Submission #1026994
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<LL> 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--) { // dp[k][n] = max(dp[k+1][n+x]+k*a[n+x]) x<=m LL val=dp[(i+1)&1][j+1]; while (q.size()>0 && q.front()<val) q.pop_front(); q.push_front(val); if ((int)q.size()>m) q.pop_back(); dp[i&1][j]=max(dp[i&1][j], q.back()+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 | 1274 Byte |
Status | WA |
Exec Time | 429 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 | 45 ms | 1792 KB |
subtask_1_3.txt | AC | 429 ms | 2176 KB |
subtask_1_4.txt | AC | 7 ms | 1792 KB |
subtask_1_5.txt | AC | 21 ms | 2176 KB |
subtask_1_6.txt | WA | 4 ms | 1792 KB |
subtask_1_7.txt | AC | 152 ms | 2176 KB |
subtask_1_8.txt | AC | 425 ms | 2176 KB |
subtask_1_9.txt | WA | 5 ms | 1792 KB |
subtask_2_1.txt | AC | 4 ms | 1792 KB |
subtask_2_2.txt | WA | 4 ms | 1792 KB |
subtask_2_3.txt | WA | 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 | WA | 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 | 55 ms | 2176 KB |
subtask_3_2.txt | WA | 56 ms | 2176 KB |
subtask_3_3.txt | WA | 54 ms | 2176 KB |
subtask_3_4.txt | WA | 45 ms | 2176 KB |
subtask_3_5.txt | AC | 7 ms | 1792 KB |
subtask_3_6.txt | WA | 35 ms | 2176 KB |
subtask_3_7.txt | AC | 55 ms | 2176 KB |
subtask_3_8.txt | AC | 9 ms | 1792 KB |
subtask_3_9.txt | WA | 56 ms | 2176 KB |
subtask_4_1.txt | AC | 429 ms | 2176 KB |
subtask_4_10.txt | AC | 333 ms | 2176 KB |
subtask_4_11.txt | WA | 429 ms | 2176 KB |
subtask_4_12.txt | WA | 429 ms | 2176 KB |
subtask_4_13.txt | WA | 429 ms | 2176 KB |
subtask_4_2.txt | WA | 428 ms | 2176 KB |
subtask_4_3.txt | AC | 427 ms | 2176 KB |
subtask_4_4.txt | AC | 423 ms | 2176 KB |
subtask_4_5.txt | WA | 363 ms | 2176 KB |
subtask_4_6.txt | AC | 45 ms | 2176 KB |
subtask_4_7.txt | WA | 231 ms | 2176 KB |
subtask_4_8.txt | AC | 420 ms | 2176 KB |
subtask_4_9.txt | WA | 198 ms | 2176 KB |