| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1075546 |
2024-08-26T07:39:15 Z |
vjudge1 |
Candies (JOI18_candies) |
C++17 |
|
662 ms |
43820 KB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define viii vector <vector <vector <int> > >
const int NM = 2e5, inf = 1e18;
int n, a[NM+5];
int res[NM/2+5][2][2], tmp[NM/2+5];
void process(int l, int r, int j, int k, int nj, int nk, viii &f, viii &g){
int cur = 0;
tmp[0] = 0;
for (int i = 1; i <= (r-l+2)/2; i++){
while (cur+1 <= i){
int val1 = f[cur][j][nj]+g[i-cur][nk][k], val2 = f[cur+1][j][nj]+g[i-cur-1][nk][k];
if (val1 < 0) val1 = -inf;
if (val2 < 0) val2 = -inf;
if (val1 <= val2) cur++;
else break;
}
tmp[i] = f[cur][j][nj]+g[i-cur][nk][k];
}
}
void dnc(int l, int r){
if (l == r){
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++){
res[0][i][j] = 0;
if (i&j) res[1][i][j] = a[l]; else res[1][i][j] = -inf;
}
return;
}
int mid = (l+r)/2;
dnc(l, mid);
vector <vector <vector <int> > > f((r-l+2)/2+1), g((r-l+2)/2+1);
for (int i = 0; i <= (r-l+2)/2; i++){
f[i].resize(2, vector <int>(2));
for (int j = 0; j < 2; j++)
for (int k = 0; k < 2; k++)
f[i][j][k] = (i <= (mid-l+2)/2 ? res[i][j][k] : -inf);
}
dnc(mid+1, r);
for (int i = 0; i <= (r-l+2)/2; i++){
g[i].resize(2, vector <int>(2));
for (int j = 0; j < 2; j++)
for (int k = 0; k < 2; k++)
g[i][j][k] = (i <= (r-mid+1)/2 ? res[i][j][k] : -inf);
}
for (int j = 0; j < 2; j++)
for (int k = 0; k < 2; k++){
process(l, r, j, k, 0, 1, f, g);
for (int i = 0; i <= (r-l+2)/2; i++)
res[i][j][k] = tmp[i];
process(l, r, j, k, 1, 0, f, g);
for (int i = 0; i <= (r-l+2)/2; i++)
res[i][j][k] = max(res[i][j][k], tmp[i]);
for (int i = 0; i <= (r-l+2)/2; i++)
for (int nj = 0; nj < 2; nj++)
for (int nk = 0; nk < 2; nk++)
if (nj <= j && nk <= k) res[i][j][k] = max(res[i][j][k], res[i][nj][nk]);
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
dnc(1, n);
for (int i = 1; i <= (n+1)/2; i++)
cout << res[i][1][1] << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
856 KB |
Output is correct |
| 2 |
Correct |
4 ms |
860 KB |
Output is correct |
| 3 |
Correct |
4 ms |
768 KB |
Output is correct |
| 4 |
Correct |
4 ms |
860 KB |
Output is correct |
| 5 |
Correct |
4 ms |
680 KB |
Output is correct |
| 6 |
Correct |
3 ms |
860 KB |
Output is correct |
| 7 |
Correct |
4 ms |
780 KB |
Output is correct |
| 8 |
Correct |
4 ms |
860 KB |
Output is correct |
| 9 |
Correct |
4 ms |
860 KB |
Output is correct |
| 10 |
Correct |
4 ms |
860 KB |
Output is correct |
| 11 |
Correct |
4 ms |
860 KB |
Output is correct |
| 12 |
Correct |
4 ms |
860 KB |
Output is correct |
| 13 |
Correct |
4 ms |
860 KB |
Output is correct |
| 14 |
Correct |
4 ms |
860 KB |
Output is correct |
| 15 |
Correct |
4 ms |
860 KB |
Output is correct |
| 16 |
Correct |
4 ms |
860 KB |
Output is correct |
| 17 |
Correct |
4 ms |
860 KB |
Output is correct |
| 18 |
Correct |
4 ms |
860 KB |
Output is correct |
| 19 |
Correct |
4 ms |
796 KB |
Output is correct |
| 20 |
Correct |
3 ms |
856 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
856 KB |
Output is correct |
| 2 |
Correct |
4 ms |
860 KB |
Output is correct |
| 3 |
Correct |
4 ms |
768 KB |
Output is correct |
| 4 |
Correct |
4 ms |
860 KB |
Output is correct |
| 5 |
Correct |
4 ms |
680 KB |
Output is correct |
| 6 |
Correct |
3 ms |
860 KB |
Output is correct |
| 7 |
Correct |
4 ms |
780 KB |
Output is correct |
| 8 |
Correct |
4 ms |
860 KB |
Output is correct |
| 9 |
Correct |
4 ms |
860 KB |
Output is correct |
| 10 |
Correct |
4 ms |
860 KB |
Output is correct |
| 11 |
Correct |
4 ms |
860 KB |
Output is correct |
| 12 |
Correct |
4 ms |
860 KB |
Output is correct |
| 13 |
Correct |
4 ms |
860 KB |
Output is correct |
| 14 |
Correct |
4 ms |
860 KB |
Output is correct |
| 15 |
Correct |
4 ms |
860 KB |
Output is correct |
| 16 |
Correct |
4 ms |
860 KB |
Output is correct |
| 17 |
Correct |
4 ms |
860 KB |
Output is correct |
| 18 |
Correct |
4 ms |
860 KB |
Output is correct |
| 19 |
Correct |
4 ms |
796 KB |
Output is correct |
| 20 |
Correct |
3 ms |
856 KB |
Output is correct |
| 21 |
Correct |
573 ms |
43560 KB |
Output is correct |
| 22 |
Correct |
578 ms |
43596 KB |
Output is correct |
| 23 |
Correct |
591 ms |
43604 KB |
Output is correct |
| 24 |
Correct |
547 ms |
43560 KB |
Output is correct |
| 25 |
Correct |
554 ms |
43556 KB |
Output is correct |
| 26 |
Correct |
550 ms |
43472 KB |
Output is correct |
| 27 |
Correct |
568 ms |
43604 KB |
Output is correct |
| 28 |
Correct |
549 ms |
43820 KB |
Output is correct |
| 29 |
Correct |
550 ms |
43604 KB |
Output is correct |
| 30 |
Correct |
567 ms |
43600 KB |
Output is correct |
| 31 |
Correct |
550 ms |
43728 KB |
Output is correct |
| 32 |
Correct |
570 ms |
43604 KB |
Output is correct |
| 33 |
Correct |
549 ms |
43444 KB |
Output is correct |
| 34 |
Correct |
609 ms |
43448 KB |
Output is correct |
| 35 |
Correct |
626 ms |
43452 KB |
Output is correct |
| 36 |
Correct |
662 ms |
43584 KB |
Output is correct |
| 37 |
Correct |
661 ms |
43600 KB |
Output is correct |
| 38 |
Correct |
607 ms |
43736 KB |
Output is correct |
| 39 |
Correct |
616 ms |
43628 KB |
Output is correct |
| 40 |
Correct |
611 ms |
43616 KB |
Output is correct |
| 41 |
Correct |
604 ms |
43572 KB |
Output is correct |
| 42 |
Correct |
581 ms |
43720 KB |
Output is correct |
| 43 |
Correct |
546 ms |
43812 KB |
Output is correct |
| 44 |
Correct |
562 ms |
43684 KB |
Output is correct |
| 45 |
Correct |
595 ms |
43604 KB |
Output is correct |
| 46 |
Correct |
548 ms |
43600 KB |
Output is correct |
| 47 |
Correct |
560 ms |
43704 KB |
Output is correct |
| 48 |
Correct |
564 ms |
43516 KB |
Output is correct |
| 49 |
Correct |
550 ms |
43600 KB |
Output is correct |
| 50 |
Correct |
532 ms |
43448 KB |
Output is correct |
