Submission #1004992
Source Code Expand
#include "bits/stdc++.h" using namespace std; #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i)) #define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i)) static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL; typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll; template<typename T, typename U> static void amin(T &x, U y) { if(y < x) x = y; } template<typename T, typename U> static void amax(T &x, U y) { if(x < y) x = y; } template<typename Val, typename Cmp = less<Val> > struct MonotonicQueue { vector<pair<Val, int>> q; int head, tail; Cmp cmp; MonotonicQueue(Cmp cmp = Cmp()) : cmp(cmp) {} void init(int n) { q.resize(n); clear(); } bool empty() const { return head == tail; } void clear() { head = tail = 0; } void enque(int i, Val x) { while(head < tail && cmp(x, q[tail - 1].first)) -- tail; q[tail ++] = make_pair(x, i); } void deque(int i) { if(head < tail && q[head].second == i) ++ head; } Val get() const { return q[head].first; } }; int main() { int N; int M; int K; while(~scanf("%d%d%d", &N, &M, &K)) { vector<int> A(N); for(int i = 0; i < N; ++ i) scanf("%d", &A[i]); vector<ll> dp(N); rep(i, N) dp[i] = A[i]; rer(k, 2, K) { MonotonicQueue<ll, greater<ll>> mq; mq.init(N); reu(i, k - 2, N) { ll x = dp[i]; mq.deque(i - M - 1); if(k - 2 < i) dp[i] = (ll)k * A[i] + mq.get(); mq.enque(i, x); } } ll ans = *max_element(dp.begin(), dp.end()); printf("%lld\n", ans); } return 0; }
Submission Info
Submission Time | |
---|---|
Task | A - Struck Out |
User | anta |
Language | C++14 (GCC 5.4.1) |
Score | 700 |
Code Size | 1709 Byte |
Status | AC |
Exec Time | 353 ms |
Memory | 2944 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:44:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d", &A[i]); ^
Judge Result
Set Name | Sample | subtask1 | subtask2 | subtask3 | All | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 100 / 100 | 200 / 200 | 300 / 300 | 100 / 100 | ||||||||||
Status |
|
|
|
|
|
Set Name | Test Cases |
---|---|
Sample | sample_1.txt, sample_2.txt, sample_3.txt |
subtask1 | sample_2.txt, subtask_1_1.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt |
subtask2 | sample_1.txt, sample_2.txt, sample_3.txt, subtask_2_1.txt, subtask_2_2.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt, subtask_2_9.txt |
subtask3 | sample_1.txt, sample_2.txt, sample_3.txt, subtask_2_1.txt, subtask_2_2.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt, subtask_2_9.txt, subtask_3_1.txt, subtask_3_2.txt, subtask_3_3.txt, subtask_3_4.txt, subtask_3_5.txt, subtask_3_6.txt, subtask_3_7.txt, subtask_3_8.txt, subtask_3_9.txt |
All | sample_1.txt, sample_2.txt, sample_3.txt, subtask_1_1.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt, subtask_2_1.txt, subtask_2_2.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt, subtask_2_9.txt, subtask_3_1.txt, subtask_3_2.txt, subtask_3_3.txt, subtask_3_4.txt, subtask_3_5.txt, subtask_3_6.txt, subtask_3_7.txt, subtask_3_8.txt, subtask_3_9.txt, subtask_4_1.txt, subtask_4_10.txt, subtask_4_11.txt, subtask_4_12.txt, subtask_4_13.txt, subtask_4_2.txt, subtask_4_3.txt, subtask_4_4.txt, subtask_4_5.txt, subtask_4_6.txt, subtask_4_7.txt, subtask_4_8.txt, subtask_4_9.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_1.txt | AC | 3 ms | 256 KB |
sample_2.txt | AC | 3 ms | 256 KB |
sample_3.txt | AC | 3 ms | 256 KB |
subtask_1_1.txt | AC | 3 ms | 256 KB |
subtask_1_2.txt | AC | 35 ms | 512 KB |
subtask_1_3.txt | AC | 353 ms | 2944 KB |
subtask_1_4.txt | AC | 5 ms | 384 KB |
subtask_1_5.txt | AC | 24 ms | 2944 KB |
subtask_1_6.txt | AC | 3 ms | 256 KB |
subtask_1_7.txt | AC | 130 ms | 2944 KB |
subtask_1_8.txt | AC | 353 ms | 2944 KB |
subtask_1_9.txt | AC | 3 ms | 256 KB |
subtask_2_1.txt | AC | 3 ms | 256 KB |
subtask_2_2.txt | AC | 3 ms | 256 KB |
subtask_2_3.txt | AC | 3 ms | 256 KB |
subtask_2_4.txt | AC | 3 ms | 256 KB |
subtask_2_5.txt | AC | 3 ms | 256 KB |
subtask_2_6.txt | AC | 3 ms | 256 KB |
subtask_2_7.txt | AC | 3 ms | 256 KB |
subtask_2_8.txt | AC | 3 ms | 256 KB |
subtask_2_9.txt | AC | 3 ms | 256 KB |
subtask_3_1.txt | AC | 52 ms | 2944 KB |
subtask_3_2.txt | AC | 52 ms | 2944 KB |
subtask_3_3.txt | AC | 50 ms | 2944 KB |
subtask_3_4.txt | AC | 42 ms | 2460 KB |
subtask_3_5.txt | AC | 5 ms | 384 KB |
subtask_3_6.txt | AC | 35 ms | 2944 KB |
subtask_3_7.txt | AC | 52 ms | 2944 KB |
subtask_3_8.txt | AC | 7 ms | 512 KB |
subtask_3_9.txt | AC | 52 ms | 2944 KB |
subtask_4_1.txt | AC | 353 ms | 2944 KB |
subtask_4_10.txt | AC | 278 ms | 2944 KB |
subtask_4_11.txt | AC | 342 ms | 2944 KB |
subtask_4_12.txt | AC | 349 ms | 2944 KB |
subtask_4_13.txt | AC | 352 ms | 2944 KB |
subtask_4_2.txt | AC | 353 ms | 2944 KB |
subtask_4_3.txt | AC | 353 ms | 2944 KB |
subtask_4_4.txt | AC | 353 ms | 2944 KB |
subtask_4_5.txt | AC | 302 ms | 2944 KB |
subtask_4_6.txt | AC | 44 ms | 2944 KB |
subtask_4_7.txt | AC | 195 ms | 2944 KB |
subtask_4_8.txt | AC | 348 ms | 2944 KB |
subtask_4_9.txt | AC | 166 ms | 2944 KB |