#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = (1ll<<60);
const int SZ = 500;
int N, M, sz[1005];
ll A[200010], x[100010], o[100010], B[1005][SZ+5];
ll XX[SZ+5][SZ+5], XO[SZ+5][SZ+5], OX[SZ+5][SZ+5], OO[SZ+5][SZ+5];
void f(int t) {
fill(OX[1], OX[1]+SZ+1, -INF); fill(XX[1], XX[1]+SZ+1, -INF); fill(OO[1], OO[1]+SZ+1, -INF); fill(XO[1], XO[1]+SZ+1, -INF);
XX[1][0]=XO[1][1]=0; OX[1][1]=OO[1][1]=B[t][1];
for (int i=2; i<=sz[t]; i++) {
fill(OX[i], OX[i]+SZ+1, -INF); fill(XX[i]+1, XX[i]+SZ+1, -INF); fill(OO[i], OO[i]+SZ+1, -INF); fill(XO[i], XO[i]+SZ+1, -INF);
for (int j=(i+1)/2; j; j--) XX[i][j]=max(XO[i-1][j], XX[i-1][j]);
for (int j=(i+1)/2; j; j--) XO[i][j]=XX[i-1][j-1]+B[t][i];
for (int j=(i+1)/2; j; j--) OX[i][j]=max(OO[i-1][j], OX[i-1][j]);
for (int j=(i+1)/2; j>=2; j--) OO[i][j]=OX[i-1][j-1]+B[t][i];
}
}
int main() {
scanf("%d", &N); M=(N+SZ-1)/SZ;
for (int i=0; i<N; i++) scanf("%d", &A[i]), B[i/SZ][i%SZ+1]=A[i], sz[i/SZ]++;
fill(x+1, x+100001, -INF); fill(o+1, o+100001, -INF);
for (int i=0; i<M; i++) {
f(i);
for (int j=(N+1)/2; j>=0; j--) {
for (int k=min(j, (sz[i]+1)/2); k>=0; k--) x[j]=max({x[j], o[j], XX[sz[i]][k]+max(x[j-k], o[j-k]), OX[sz[i]][k]+x[j-k]});
for (int k=min(j, (sz[i]+1)/2); k; k--) o[j]=max({o[j], XO[sz[i]][k]+max(x[j-k], o[j-k]), OO[sz[i]][k]+x[j-k]});
}
}
for (int i=1; i<=(N+1)/2; i++) printf("%lld\n", max(x[i], o[i]));
return 0;
}
Compilation message
candies.cpp: In function 'int main()':
candies.cpp:25:43: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'll* {aka long long int*}' [-Wformat=]
for (int i=0; i<N; i++) scanf("%d", &A[i]), B[i/SZ][i%SZ+1]=A[i], sz[i/SZ]++;
~~~~~^
candies.cpp:24:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N); M=(N+SZ-1)/SZ;
~~~~~^~~~~~~~~~
candies.cpp:25:66: 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]), B[i/SZ][i%SZ+1]=A[i], sz[i/SZ]++;
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
9848 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
9848 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
