Submission #1012477
Source Code Expand
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <deque>
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];
int deq[333][111111];
int s[333], t[333];
struct S {
};
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;
}
ll res = 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] = dp4[j][deq[j][s[j]]] + a[i-1]*(j+1);
res = max(res, dp4[j+1][i]);
// 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", res);
}
return 0;
}
Submission Info
Submission Time |
|
Task |
A - Struck Out |
User |
roxion1377 |
Language |
C++14 (GCC 5.4.1) |
Score |
700 |
Code Size |
3426 Byte |
Status |
AC |
Exec Time |
1154 ms |
Memory |
408320 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:30: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:32: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 |
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 |
334 ms |
289280 KB |
sample_2.txt |
AC |
334 ms |
289280 KB |
sample_3.txt |
AC |
338 ms |
289408 KB |
subtask_1_1.txt |
AC |
335 ms |
289536 KB |
subtask_1_2.txt |
AC |
402 ms |
290688 KB |
subtask_1_3.txt |
AC |
1149 ms |
291712 KB |
subtask_1_4.txt |
AC |
335 ms |
289536 KB |
subtask_1_5.txt |
AC |
354 ms |
290560 KB |
subtask_1_6.txt |
AC |
339 ms |
290176 KB |
subtask_1_7.txt |
AC |
487 ms |
290944 KB |
subtask_1_8.txt |
AC |
1140 ms |
291712 KB |
subtask_1_9.txt |
AC |
344 ms |
290560 KB |
subtask_2_1.txt |
AC |
336 ms |
289408 KB |
subtask_2_2.txt |
AC |
337 ms |
289536 KB |
subtask_2_3.txt |
AC |
336 ms |
289408 KB |
subtask_2_4.txt |
AC |
337 ms |
289408 KB |
subtask_2_5.txt |
AC |
334 ms |
289408 KB |
subtask_2_6.txt |
AC |
337 ms |
289408 KB |
subtask_2_7.txt |
AC |
335 ms |
289408 KB |
subtask_2_8.txt |
AC |
338 ms |
289408 KB |
subtask_2_9.txt |
AC |
333 ms |
289408 KB |
subtask_3_1.txt |
AC |
380 ms |
290560 KB |
subtask_3_2.txt |
AC |
381 ms |
290560 KB |
subtask_3_3.txt |
AC |
376 ms |
290560 KB |
subtask_3_4.txt |
AC |
373 ms |
290432 KB |
subtask_3_5.txt |
AC |
339 ms |
289536 KB |
subtask_3_6.txt |
AC |
365 ms |
290560 KB |
subtask_3_7.txt |
AC |
378 ms |
290560 KB |
subtask_3_8.txt |
AC |
352 ms |
289536 KB |
subtask_3_9.txt |
AC |
374 ms |
290688 KB |
subtask_4_1.txt |
AC |
1154 ms |
291712 KB |
subtask_4_10.txt |
AC |
1106 ms |
408320 KB |
subtask_4_11.txt |
AC |
931 ms |
301824 KB |
subtask_4_12.txt |
AC |
935 ms |
296704 KB |
subtask_4_13.txt |
AC |
953 ms |
293632 KB |
subtask_4_2.txt |
AC |
1007 ms |
292224 KB |
subtask_4_3.txt |
AC |
1135 ms |
291712 KB |
subtask_4_4.txt |
AC |
1148 ms |
291712 KB |
subtask_4_5.txt |
AC |
954 ms |
291584 KB |
subtask_4_6.txt |
AC |
367 ms |
290560 KB |
subtask_4_7.txt |
AC |
550 ms |
291328 KB |
subtask_4_8.txt |
AC |
1130 ms |
291712 KB |
subtask_4_9.txt |
AC |
532 ms |
291072 KB |