Submission #1012458
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];
ll dp3[111111][333];
priority_queue<ll> q[333], dq[333];
ll dp4[333][111111];
ll deq[333][111111];
ll s[333], t[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 if (k <= 30 && false) {
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));
}
if (i-m >= 0) {
for (int j = 0; j < k; j++) {
if (dp3[i-m][j] >= 0) {
dq[j].push(dp3[i-m][j]);
}
}
}
}
printf("%lld\n", q[k].top());
} else {
memset(dp4, -1, sizeof(dp4));
for (int i = 0; i < n; i++) {
dp4[0][i] = 0;
deq[0][t[0]++] = 0;
}
for (int i = 1; i <= n; i++) {
for (int j = k-1; j >= 0; j--) {
if (s[j] < t[j]) {
dp4[j+1][i] = max(s[j+1] < t[j+1] ?
dp4[j+1][deq[j+1][s[j+1]]] : 0,
dp4[j][deq[j][s[j]]] + a[i-1]*(j+1));
// printf("%d %d max: %lld\n", i, j, dp4[j][deq[j][s[j]]]);
while (s[j+1] < t[j+1] &&
dp4[j+1][deq[j+1][t[j+1]-1]] <= dp4[j+1][i]) --t[j+1];
deq[j+1][t[j+1]++] = i;
if (i-m >= 0) {
if (j > 0 && deq[j][s[j]] == i-m) {
++s[j];
}
}
}
}
}
/*
for (int ii = 0; ii <= k; ii++) {
for (int jj = 0; jj <= n; jj++) {
printf("%5lld", dp4[ii][jj]);
}
puts("");
}
// */
printf("%lld\n", dp4[k][n]);
}
return 0;
}
Submission Info
Submission Time |
|
Task |
A - Struck Out |
User |
roxion1377 |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
3447 Byte |
Status |
WA |
Exec Time |
1100 ms |
Memory |
525312 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:25: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:27: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 |
100 / 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 |
280 ms |
289408 KB |
sample_2.txt |
AC |
281 ms |
289280 KB |
sample_3.txt |
AC |
282 ms |
289408 KB |
subtask_1_1.txt |
AC |
282 ms |
289408 KB |
subtask_1_2.txt |
AC |
333 ms |
290688 KB |
subtask_1_3.txt |
AC |
813 ms |
292096 KB |
subtask_1_4.txt |
AC |
284 ms |
289536 KB |
subtask_1_5.txt |
AC |
296 ms |
290944 KB |
subtask_1_6.txt |
AC |
282 ms |
290176 KB |
subtask_1_7.txt |
AC |
402 ms |
291328 KB |
subtask_1_8.txt |
AC |
813 ms |
292096 KB |
subtask_1_9.txt |
AC |
284 ms |
290560 KB |
subtask_2_1.txt |
AC |
280 ms |
289408 KB |
subtask_2_2.txt |
WA |
280 ms |
289408 KB |
subtask_2_3.txt |
WA |
280 ms |
289408 KB |
subtask_2_4.txt |
AC |
281 ms |
289408 KB |
subtask_2_5.txt |
AC |
279 ms |
289408 KB |
subtask_2_6.txt |
AC |
280 ms |
289408 KB |
subtask_2_7.txt |
WA |
281 ms |
289408 KB |
subtask_2_8.txt |
AC |
281 ms |
289408 KB |
subtask_2_9.txt |
AC |
279 ms |
289408 KB |
subtask_3_1.txt |
AC |
315 ms |
291072 KB |
subtask_3_2.txt |
WA |
316 ms |
291072 KB |
subtask_3_3.txt |
WA |
314 ms |
291072 KB |
subtask_3_4.txt |
WA |
308 ms |
290688 KB |
subtask_3_5.txt |
AC |
279 ms |
289536 KB |
subtask_3_6.txt |
WA |
300 ms |
290944 KB |
subtask_3_7.txt |
AC |
316 ms |
291072 KB |
subtask_3_8.txt |
AC |
282 ms |
289664 KB |
subtask_3_9.txt |
WA |
313 ms |
291072 KB |
subtask_4_1.txt |
AC |
820 ms |
292096 KB |
subtask_4_10.txt |
MLE |
1100 ms |
525312 KB |
subtask_4_11.txt |
WA |
833 ms |
292096 KB |
subtask_4_12.txt |
WA |
834 ms |
292096 KB |
subtask_4_13.txt |
WA |
820 ms |
292096 KB |
subtask_4_2.txt |
WA |
824 ms |
292096 KB |
subtask_4_3.txt |
AC |
813 ms |
292096 KB |
subtask_4_4.txt |
AC |
822 ms |
292096 KB |
subtask_4_5.txt |
WA |
658 ms |
291968 KB |
subtask_4_6.txt |
AC |
306 ms |
290944 KB |
subtask_4_7.txt |
WA |
447 ms |
291584 KB |
subtask_4_8.txt |
AC |
816 ms |
292096 KB |
subtask_4_9.txt |
WA |
426 ms |
291456 KB |