| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 100783 |
2019-03-14T10:51:13 Z |
JPN20 |
Candies (JOI18_candies) |
C++17 |
|
5000 ms |
10752 KB |
#include <bits/stdc++.h>
using namespace std;
struct Node{
vector<long long> p[4];
};
vector<long long> check(vector<long long>A, vector<long long>B) {
vector<long long>ans;
int maxs = A.size() - 1 + B.size() - 1;
for (int i = 0; i <= maxs; i++) {
int L = 0, R = A.size(), c1, c2;
if (i >= (int)B.size()) L = i - ((int)B.size() - 1);
if (i < (int)A.size()) R = i + 1;
int cl = L, cr = R;
for (int j = 0; j < 30; j++) {
c1 = (L + L + R) / 3;
c2 = (L + R + R) / 3;
long long E1 = A[c1] + B[i - c1];
long long E2 = A[c2] + B[i - c2];
if (E1 < E2) L = c1;
else R = c2;
}
long long rets = 0;
for (int j = -3; j <= 3; j++) {
int ss = c1 + j; if (ss < cl || cr <= ss) continue;
rets = max(rets, A[ss] + B[i - ss]);
}
ans.push_back(rets);
}
return ans;
}
Node calc(Node A1, Node A2) {
// i = 1 or 3 : 一番後ろに飴がある
// i = 2 or 3 : 一番前に飴がある
Node E;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if ((i == 1 || i == 3) && (j == 2 || j == 3)) continue;
vector<long long> I = check(A1.p[i], A2.p[j]);
int ty = 0; if (i == 2 || i == 3) ty += 2; if (j == 1 || j == 3) ty += 1;
for (int j = 0; j < (int)I.size(); j++) {
if ((int)E.p[ty].size() == j) E.p[ty].push_back(I[j]);
else E.p[ty][j] = max(E.p[ty][j], I[j]);
}
}
}
return E;
}
long long N, A[200009], C[200009];
Node solve(int l, int r) {
if (l + 1 == r) {
Node I;
I.p[0] = {0};
I.p[1] = {0};
I.p[2] = {0};
I.p[3] = {0, A[l]};
return I;
}
Node LL = solve(l, (l + r) / 2);
Node RR = solve((l + r) / 2, r);
return calc(LL, RR);
}
int main() {
scanf("%lld", &N);
for (int i = 1; i <= N; i++) {
scanf("%lld", &A[i]);
}
Node T = solve(1, N + 1);
for (int i = 0; i < 4; i++) {
for (int j = 0; j < T.p[i].size(); j++) C[j] = max(C[j], T.p[i][j]);
}
for (int i = 1; i <= (N + 1) / 2; i++) printf("%lld\n", C[i]);
return 0;
}
Compilation message
candies.cpp: In function 'int main()':
candies.cpp:82:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < T.p[i].size(); j++) C[j] = max(C[j], T.p[i][j]);
~~^~~~~~~~~~~~~~~
candies.cpp:75:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld", &N);
~~~~~^~~~~~~~~~~~
candies.cpp:77:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld", &A[i]);
~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
46 ms |
504 KB |
Output is correct |
| 2 |
Correct |
54 ms |
504 KB |
Output is correct |
| 3 |
Correct |
45 ms |
504 KB |
Output is correct |
| 4 |
Correct |
48 ms |
504 KB |
Output is correct |
| 5 |
Correct |
44 ms |
500 KB |
Output is correct |
| 6 |
Correct |
47 ms |
504 KB |
Output is correct |
| 7 |
Correct |
43 ms |
504 KB |
Output is correct |
| 8 |
Correct |
42 ms |
504 KB |
Output is correct |
| 9 |
Correct |
46 ms |
500 KB |
Output is correct |
| 10 |
Correct |
50 ms |
504 KB |
Output is correct |
| 11 |
Correct |
45 ms |
504 KB |
Output is correct |
| 12 |
Correct |
43 ms |
508 KB |
Output is correct |
| 13 |
Correct |
44 ms |
504 KB |
Output is correct |
| 14 |
Correct |
45 ms |
504 KB |
Output is correct |
| 15 |
Correct |
49 ms |
572 KB |
Output is correct |
| 16 |
Correct |
46 ms |
504 KB |
Output is correct |
| 17 |
Correct |
53 ms |
504 KB |
Output is correct |
| 18 |
Correct |
42 ms |
504 KB |
Output is correct |
| 19 |
Correct |
44 ms |
504 KB |
Output is correct |
| 20 |
Correct |
44 ms |
504 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
46 ms |
504 KB |
Output is correct |
| 2 |
Correct |
54 ms |
504 KB |
Output is correct |
| 3 |
Correct |
45 ms |
504 KB |
Output is correct |
| 4 |
Correct |
48 ms |
504 KB |
Output is correct |
| 5 |
Correct |
44 ms |
500 KB |
Output is correct |
| 6 |
Correct |
47 ms |
504 KB |
Output is correct |
| 7 |
Correct |
43 ms |
504 KB |
Output is correct |
| 8 |
Correct |
42 ms |
504 KB |
Output is correct |
| 9 |
Correct |
46 ms |
500 KB |
Output is correct |
| 10 |
Correct |
50 ms |
504 KB |
Output is correct |
| 11 |
Correct |
45 ms |
504 KB |
Output is correct |
| 12 |
Correct |
43 ms |
508 KB |
Output is correct |
| 13 |
Correct |
44 ms |
504 KB |
Output is correct |
| 14 |
Correct |
45 ms |
504 KB |
Output is correct |
| 15 |
Correct |
49 ms |
572 KB |
Output is correct |
| 16 |
Correct |
46 ms |
504 KB |
Output is correct |
| 17 |
Correct |
53 ms |
504 KB |
Output is correct |
| 18 |
Correct |
42 ms |
504 KB |
Output is correct |
| 19 |
Correct |
44 ms |
504 KB |
Output is correct |
| 20 |
Correct |
44 ms |
504 KB |
Output is correct |
| 21 |
Execution timed out |
5036 ms |
10752 KB |
Time limit exceeded |
| 22 |
Halted |
0 ms |
0 KB |
- |
