Submission #1027007
Source Code Expand
#include <vector> #include <list> #include <map> #include <set> #include <deque> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <ctime> #include <queue> #include <fstream> #include <cstring> using namespace std; typedef long long LL; #define MAXN 100010 int n, m, k; int a[MAXN]; LL dp[2][MAXN]; deque<pair<LL, int> > q; int main() { //freopen("struck_out.in", "r", stdin); cin>>n>>m>>k; for (int i=0;i<n;i++) scanf("%d", &a[i]); memset(dp, 0, sizeof(dp)); for (int i=0;i<n;i++) { dp[(k-1)&1][i] = 1LL*k*a[i]; //cout<<k-1<<" "<<i<<" = "<<dp[k-1][i]<<endl; } for (int i=k-2;i>=0;i--) { while (q.size()>0) q.pop_back(); for (int j=n-2;j>=0;j--) { LL val=dp[(i+1)&1][j+1]; while (q.size()>0 && q.front().first<val) q.pop_front(); q.push_front(make_pair(val, j+1)); while (q.size()>0 && q.back().second-j-1>=m) q.pop_back(); dp[i&1][j]=max(dp[i&1][j], q.back().first+1LL*(i+1)*a[j]); //cout<<i<<" "<<j<<" = "<<dp[i][j]<<endl; } } LL ret=0; for (int i=0;i<n;i++) ret=max(ret, dp[0][i]); cout<<ret<<endl; }
Submission Info
Submission Time | |
---|---|
Task | A - Struck Out |
User | culaucon |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1288 Byte |
Status | WA |
Exec Time | 496 ms |
Memory | 2176 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:35:42: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] for (int i=0;i<n;i++) scanf("%d", &a[i]); ^
Judge Result
Set Name | Sample | subtask1 | subtask2 | subtask3 | All | ||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 100 | 0 / 200 | 0 / 300 | 0 / 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 | 4 ms | 1792 KB |
sample_2.txt | AC | 4 ms | 1792 KB |
sample_3.txt | AC | 4 ms | 1792 KB |
subtask_1_1.txt | AC | 4 ms | 1792 KB |
subtask_1_2.txt | AC | 50 ms | 1792 KB |
subtask_1_3.txt | AC | 477 ms | 2176 KB |
subtask_1_4.txt | AC | 7 ms | 1792 KB |
subtask_1_5.txt | AC | 22 ms | 2176 KB |
subtask_1_6.txt | WA | 5 ms | 1792 KB |
subtask_1_7.txt | AC | 168 ms | 2176 KB |
subtask_1_8.txt | AC | 471 ms | 2176 KB |
subtask_1_9.txt | WA | 6 ms | 1792 KB |
subtask_2_1.txt | AC | 4 ms | 1792 KB |
subtask_2_2.txt | AC | 4 ms | 1792 KB |
subtask_2_3.txt | AC | 4 ms | 1792 KB |
subtask_2_4.txt | AC | 4 ms | 1792 KB |
subtask_2_5.txt | WA | 4 ms | 1792 KB |
subtask_2_6.txt | WA | 4 ms | 1792 KB |
subtask_2_7.txt | AC | 4 ms | 1792 KB |
subtask_2_8.txt | AC | 4 ms | 1792 KB |
subtask_2_9.txt | AC | 4 ms | 1792 KB |
subtask_3_1.txt | AC | 60 ms | 2176 KB |
subtask_3_2.txt | AC | 61 ms | 2176 KB |
subtask_3_3.txt | AC | 59 ms | 2176 KB |
subtask_3_4.txt | AC | 49 ms | 2176 KB |
subtask_3_5.txt | AC | 7 ms | 1792 KB |
subtask_3_6.txt | AC | 38 ms | 2176 KB |
subtask_3_7.txt | AC | 61 ms | 2176 KB |
subtask_3_8.txt | AC | 10 ms | 1792 KB |
subtask_3_9.txt | AC | 61 ms | 2176 KB |
subtask_4_1.txt | AC | 475 ms | 2176 KB |
subtask_4_10.txt | AC | 408 ms | 2176 KB |
subtask_4_11.txt | AC | 496 ms | 2176 KB |
subtask_4_12.txt | AC | 490 ms | 2176 KB |
subtask_4_13.txt | AC | 483 ms | 2176 KB |
subtask_4_2.txt | AC | 479 ms | 2176 KB |
subtask_4_3.txt | AC | 477 ms | 2176 KB |
subtask_4_4.txt | AC | 478 ms | 2176 KB |
subtask_4_5.txt | AC | 406 ms | 2176 KB |
subtask_4_6.txt | AC | 49 ms | 2176 KB |
subtask_4_7.txt | AC | 259 ms | 2176 KB |
subtask_4_8.txt | AC | 468 ms | 2176 KB |
subtask_4_9.txt | AC | 220 ms | 2176 KB |