# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
61502 |
2018-07-26T05:57:53 Z |
ainta(#1774) |
Homecoming (BOI18_homecoming) |
C++11 |
|
172 ms |
16272 KB |
#include "homecoming.h"
#include <algorithm>
#define N_ 2010000
using namespace std;
int A[N_], B[N_], n, K;
long long D[N_][2], res;
void Do() {
int i;
for (i = 0; i <= n; i++)D[i][0] = D[i][1] = -1e18;
D[1][0] = B[1];
for (i = 2; i <= n; i++) {
D[i][0] = D[i - 1][0] + B[i];
if (i >= K)D[i][0] = max(D[i][0], D[i - K + 1][1]);
D[i][1] = max(max(D[i - 1][1], D[i - 1][0]) + A[i], D[i][0]);
}
res = max(res, D[n][0]);
for (i = 0; i <= n; i++)D[i][0] = D[i][1] = -1e18;
D[1][1] = A[1];
for (i = 2; i <= n; i++) {
D[i][0] = D[i - 1][0] + B[i];
if (i >= K)D[i][0] = max(D[i][0], D[i - K + 1][1]);
D[i][1] = max(max(D[i - 1][1], D[i - 1][0]) + A[i], D[i][0]);
}
res = max(res, max(D[n][0], D[n][1]));
}
void Rotate() {
int i;
int ta = A[1], tb = B[1];
for (i = 1; i < n; i++)A[i] = A[i + 1], B[i] = B[i + 1];
A[n] = ta, B[n] = tb;
}
long long int solve(int N, int k, int *a, int *b) {
int i;
res = 0;
n = N, K = k;
if (K == 1) {
long long r = 0;
for (i = 0; i < n; i++) {
r += max(a[i]-b[i],0);
}
return r;
}
for (i = 1; i <= n; i++)A[i] = a[i - 1], B[i] = b[i - 1];
for (i = 1; i <= n; i++)res += A[i];
//for (i = 0; i <= K; i++) {
Do();
//Rotate();
//}
for (i = 1; i <= n; i++)res -= B[i];
return res;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
412 KB |
Output is correct |
4 |
Correct |
3 ms |
596 KB |
Output is correct |
5 |
Correct |
3 ms |
596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
412 KB |
Output is correct |
4 |
Correct |
3 ms |
596 KB |
Output is correct |
5 |
Correct |
3 ms |
596 KB |
Output is correct |
6 |
Correct |
2 ms |
676 KB |
Output is correct |
7 |
Correct |
3 ms |
676 KB |
Output is correct |
8 |
Correct |
4 ms |
676 KB |
Output is correct |
9 |
Incorrect |
5 ms |
700 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
75 ms |
16192 KB |
Output is correct |
2 |
Correct |
6 ms |
16192 KB |
Output is correct |
3 |
Correct |
172 ms |
16272 KB |
Output is correct |
4 |
Incorrect |
5 ms |
16272 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
412 KB |
Output is correct |
4 |
Correct |
3 ms |
596 KB |
Output is correct |
5 |
Correct |
3 ms |
596 KB |
Output is correct |
6 |
Correct |
2 ms |
676 KB |
Output is correct |
7 |
Correct |
3 ms |
676 KB |
Output is correct |
8 |
Correct |
4 ms |
676 KB |
Output is correct |
9 |
Incorrect |
5 ms |
700 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |