Submission #1012406
Source Code Expand
#include <cstdio> #include <cstring> #include <algorithm> #include <queue> using namespace std; typedef long long ll; int n, m, k; ll a[111111]; ll dp[333][33]; ll dp2[2][333]; // dp[111111][333]; ll dp3[111111][333]; priority_queue<ll> q[333], dq[333]; int main(void) { scanf("%d%d%d", &n, &m, &k); for (int i = 0; i < n; i++) { scanf("%lld", a+i); } if (n == m && false) { ll res = 0; memset(dp2, -1, sizeof(dp2)); dp2[1][0] = 0; for (int i = 0; i < n; i++) { dp2[i%2][0] = 0; for (int j = 1; j <= k; j++) { if (dp2[i%2][j-1] >= 0) { dp2[(i+1)%2][j] = max({ dp2[(i+1)%2][j], dp2[i%2][j-1] + a[i]*j, dp2[i%2][j] }); } } for (int j = 0; j <= k; j++) { res = max(res, dp2[(i+1)%2][j]); if (dp2[i%2][j] >= 0) { dp2[i%2][j] = 0; } // printf("%5lld", dp2[(i+1)%2][j]); } // puts(""); } printf("%lld\n", res); } else if (n <= 300 && k <= 30 && false) { memset(dp, -1, sizeof(dp)); for (int i = 0; i <= n; i++) { dp[i][0] = 0; } for (int i = 1; i <= n; i++) { for (int j = 0; j < k; j++) { for (int l = 1; l <= m && i-l >= 0; l++) { if (dp[i-l][j] >= 0) { dp[i][j+1] = max(dp[i][j+1], dp[i-l][j]+a[i-1]*(j+1)); } } } } ll res = 0; for (int i = 0; i <= n+1; i++) { for (int j = 0; j <= k; j++) { // printf("%5lld", dp[i][j]); res = max(res, dp[i][j]); } // puts(""); } printf("%lld\n", res); } else { q[0].push(0); memset(dp3, -1, sizeof(dp3)); for (int i = 1; i <= n; i++) { for (int j = k-1; j >= 0; j--) { if (q[j].size() == 0) continue; while (!dq[j].empty() && q[j].top() == dq[j].top()) { q[j].pop(); dq[j].pop(); } dp3[i][j+1] = q[j].top()+a[i-1]*(j+1); q[j+1].push(q[j].top()+a[i-1]*(j+1)); /* dp[i][j+1]; for (int l = 1; l <= m && i-l >= 0; l++) { if (dp[i-l][j] >= 0) { dp[i][j+1] = max(dp[i][j+1], dp[i-l][j]+a[i-1]*(j+1)); } } */ } } printf("%lld\n", q[k].top()); } return 0; }
Submission Info
Submission Time | |
---|---|
Task | A - Struck Out |
User | roxion1377 |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 2467 Byte |
Status | WA |
Exec Time | 2133 ms |
Memory | 466584 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:20:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d%d%d", &n, &m, &k); ^ ./Main.cpp:22:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%lld", 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 | 298 ms | 289280 KB |
sample_2.txt | AC | 300 ms | 289280 KB |
sample_3.txt | AC | 300 ms | 289280 KB |
subtask_1_1.txt | AC | 301 ms | 289408 KB |
subtask_1_2.txt | AC | 480 ms | 320896 KB |
subtask_1_3.txt | TLE | 2132 ms | 456852 KB |
subtask_1_4.txt | AC | 306 ms | 291200 KB |
subtask_1_5.txt | AC | 341 ms | 294284 KB |
subtask_1_6.txt | AC | 299 ms | 289536 KB |
subtask_1_7.txt | AC | 875 ms | 371164 KB |
subtask_1_8.txt | TLE | 2132 ms | 458132 KB |
subtask_1_9.txt | AC | 303 ms | 290432 KB |
subtask_2_1.txt | AC | 298 ms | 289408 KB |
subtask_2_2.txt | WA | 299 ms | 289408 KB |
subtask_2_3.txt | WA | 300 ms | 289408 KB |
subtask_2_4.txt | AC | 300 ms | 289408 KB |
subtask_2_5.txt | AC | 298 ms | 289280 KB |
subtask_2_6.txt | AC | 298 ms | 289280 KB |
subtask_2_7.txt | WA | 299 ms | 289408 KB |
subtask_2_8.txt | AC | 299 ms | 289408 KB |
subtask_2_9.txt | AC | 300 ms | 289408 KB |
subtask_3_1.txt | AC | 458 ms | 313708 KB |
subtask_3_2.txt | WA | 456 ms | 313708 KB |
subtask_3_3.txt | WA | 450 ms | 312996 KB |
subtask_3_4.txt | WA | 428 ms | 308972 KB |
subtask_3_5.txt | AC | 305 ms | 291072 KB |
subtask_3_6.txt | WA | 385 ms | 302192 KB |
subtask_3_7.txt | AC | 457 ms | 313708 KB |
subtask_3_8.txt | AC | 311 ms | 292864 KB |
subtask_3_9.txt | WA | 457 ms | 313708 KB |
subtask_4_1.txt | TLE | 2132 ms | 459156 KB |
subtask_4_10.txt | TLE | 2132 ms | 458004 KB |
subtask_4_11.txt | TLE | 2132 ms | 458900 KB |
subtask_4_12.txt | TLE | 2132 ms | 456724 KB |
subtask_4_13.txt | TLE | 2132 ms | 459156 KB |
subtask_4_2.txt | TLE | 2132 ms | 458644 KB |
subtask_4_3.txt | TLE | 2132 ms | 456980 KB |
subtask_4_4.txt | TLE | 2132 ms | 457748 KB |
subtask_4_5.txt | TLE | 2133 ms | 466584 KB |
subtask_4_6.txt | AC | 419 ms | 308328 KB |
subtask_4_7.txt | WA | 1403 ms | 417632 KB |
subtask_4_8.txt | TLE | 2132 ms | 459924 KB |
subtask_4_9.txt | WA | 1155 ms | 396724 KB |