#include<iostream>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<utility>
#include<algorithm>
using namespace std;
#define int long long
#define vel vector<int>
#define vvel vector<vel>
#define vvvel vector<vvel>
#define veb vector<bool>
void mmax(int &a, int b) { a = max(a, b); }
vel com(vel &u, vel &v) {
vel ans(1,0);
int mu = 0; int mv = 0;
int su = u.size();
int sv = v.size();
while (mu < su - 1 or mv < sv - 1) {
int nu = mu + 1;
int nv = mv + 1;
if (nu == su) { mv++; }
else if (nv == sv) { mu++; }
else if (u[nu] - u[mu] > v[nv] - v[mv]) { mu++; }
else { mv++; }
ans.push_back(u[mu] + v[mv]);
}
return ans;
}
vel r_no(int st, int to, vel &a) {
int siz = to - st;
int ko = (siz + 3) / 2;
vvel dp(siz+1, vel(ko, -1));
dp[0][0] = 0;
dp[1][0] = 0; dp[1][1] = a[st];
for (int i = 2; i <= siz; i++) {
dp[i] = dp[i - 1];
for (int j = 1; j < ko; j++) {
if (dp[i - 2][j - 1] != -1) { mmax(dp[i][j], dp[i - 2][j - 1] + a[st + i - 1]); }
}
}
return dp[siz];
}
signed main() {
int n; cin >> n;
vel a(n);
for (int i = 0; i < n; i++) { cin >> a[i]; }
int ko = (n + 3) / 2;
if (n > 2000) {
vel x = r_no(0, n, a);
for (int i = 0; i < x.size(); i++) { cout << x[i] << endl; }
}
else {
int range = 500;
vel dp0 = r_no(0, range, a);
vel dp1 = r_no(0, range - 1, a);
int st1 = 0;
for (int i = 2; i*range <= n - range; i++) {
int st = (i - 1)*range;
int to = i * range; mmax(st1, to);
vel x0 = r_no(st, to, a);
vel x1 = r_no(st + 1, to, a);
vel qdp0 = com(dp1, x0); x0.clear();
vel rdp0 = com(dp0, x1); x1.clear();
vel y0 = r_no(st, to - 1, a);
vel y1 = r_no(st + 1, to - 1, a);
vel qdp1 = com(dp1, y0); y0.clear();
vel rdp1 = com(dp0, y1); y1.clear();
dp0 = vel(0);
for (int i = 0; i<qdp0.size() ; i++) { dp0.push_back(max(qdp0[i], rdp0[i]));}
dp1 = vel(0);
for (int i = 0; i < rdp1.size(); i++) { dp1.push_back(max(qdp1[i], rdp1[i])); }
dp1.push_back(qdp1[qdp1.size() - 1]);
}
vel x = r_no(st1, n, a);
vel y = r_no(st1 + 1, n, a);
vel qans = com(dp0, y);
vel rans = com(dp1, x);
for (int i = 1; i < ko; i++) { cout << max(qans[i], rans[i]) << endl; }
}
return 0;
}
Compilation message
candies.cpp: In function 'int main()':
candies.cpp:52:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < x.size(); i++) { cout << x[i] << endl; }
~~^~~~~~~~~~
candies.cpp:71:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i<qdp0.size() ; i++) { dp0.push_back(max(qdp0[i], rdp0[i]));}
~^~~~~~~~~~~~
candies.cpp:73:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < rdp1.size(); i++) { dp1.push_back(max(qdp1[i], rdp1[i])); }
~~^~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
13 ms |
1432 KB |
Output is correct |
| 2 |
Correct |
14 ms |
1468 KB |
Output is correct |
| 3 |
Correct |
12 ms |
1432 KB |
Output is correct |
| 4 |
Correct |
13 ms |
1468 KB |
Output is correct |
| 5 |
Correct |
12 ms |
1468 KB |
Output is correct |
| 6 |
Correct |
12 ms |
1468 KB |
Output is correct |
| 7 |
Correct |
12 ms |
1432 KB |
Output is correct |
| 8 |
Correct |
15 ms |
1432 KB |
Output is correct |
| 9 |
Correct |
18 ms |
1416 KB |
Output is correct |
| 10 |
Correct |
13 ms |
1384 KB |
Output is correct |
| 11 |
Correct |
15 ms |
4316 KB |
Output is correct |
| 12 |
Correct |
17 ms |
4316 KB |
Output is correct |
| 13 |
Correct |
17 ms |
4316 KB |
Output is correct |
| 14 |
Correct |
14 ms |
4316 KB |
Output is correct |
| 15 |
Correct |
22 ms |
4316 KB |
Output is correct |
| 16 |
Correct |
16 ms |
4316 KB |
Output is correct |
| 17 |
Correct |
16 ms |
4392 KB |
Output is correct |
| 18 |
Correct |
18 ms |
4392 KB |
Output is correct |
| 19 |
Correct |
16 ms |
4316 KB |
Output is correct |
| 20 |
Correct |
15 ms |
4316 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
13 ms |
1432 KB |
Output is correct |
| 2 |
Correct |
14 ms |
1468 KB |
Output is correct |
| 3 |
Correct |
12 ms |
1432 KB |
Output is correct |
| 4 |
Correct |
13 ms |
1468 KB |
Output is correct |
| 5 |
Correct |
12 ms |
1468 KB |
Output is correct |
| 6 |
Correct |
12 ms |
1468 KB |
Output is correct |
| 7 |
Correct |
12 ms |
1432 KB |
Output is correct |
| 8 |
Correct |
15 ms |
1432 KB |
Output is correct |
| 9 |
Correct |
18 ms |
1416 KB |
Output is correct |
| 10 |
Correct |
13 ms |
1384 KB |
Output is correct |
| 11 |
Correct |
15 ms |
4316 KB |
Output is correct |
| 12 |
Correct |
17 ms |
4316 KB |
Output is correct |
| 13 |
Correct |
17 ms |
4316 KB |
Output is correct |
| 14 |
Correct |
14 ms |
4316 KB |
Output is correct |
| 15 |
Correct |
22 ms |
4316 KB |
Output is correct |
| 16 |
Correct |
16 ms |
4316 KB |
Output is correct |
| 17 |
Correct |
16 ms |
4392 KB |
Output is correct |
| 18 |
Correct |
18 ms |
4392 KB |
Output is correct |
| 19 |
Correct |
16 ms |
4316 KB |
Output is correct |
| 20 |
Correct |
15 ms |
4316 KB |
Output is correct |
| 21 |
Runtime error |
528 ms |
525312 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 22 |
Halted |
0 ms |
0 KB |
- |
