# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
61514 |
2018-07-26T06:20:41 Z |
koosaga(#1775) |
Homecoming (BOI18_homecoming) |
C++11 |
|
1000 ms |
20560 KB |
#include<bits/stdc++.h>
//#include "homecoming.h"
using namespace std;
using lint = long long;
const int MAXN = 4000005;
lint a[MAXN], b[MAXN], dp[MAXN];
long long solve(int N, int K, int *A, int *B){
for(int i=1; i<=N; i++){
a[i] = a[i+N] = A[i-1];
b[i] = b[i+N] = B[i-1];
}
for(int i=1; i<=2*N; i++){
a[i] += a[i-1];
b[i] += b[i-1];
}
if(K == N){
return max(0ll, a[N] - b[N]);
}
// First DP : Go across the interval
lint ans = max(0ll, a[N] - b[N]);
dp[N+1] = 0;
for(int i=N; i; i--){
dp[i] = a[N] - a[i-1] - (b[N] - b[i-1]); // [i, N]
dp[i] = max(dp[i], dp[i+1]); // Fuck it
for(int j=i+1; j+K-2<=N; j++){
dp[i] = max(dp[i], dp[j] - (b[j + K - 2] - b[i-1]) + (a[j-1] - a[i-1]));
}
if(i + K - 2 <= N) ans = max(ans, dp[i] + a[i-1] - b[i + K - 2]);
}
dp[N+1] = 0;
// Second DP : Act like it never existed
for(int i=N; i; i--){
dp[i] = dp[i+1];
for(int j=i+1; j<=N+1; j++){
dp[i] = max(dp[i], dp[j] - (b[j+K-2] - b[i-1]) + (a[j-1] - a[i-1]));
}
}
ans = max(ans, dp[1]);
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
376 KB |
Output is correct |
2 |
Correct |
3 ms |
488 KB |
Output is correct |
3 |
Correct |
3 ms |
488 KB |
Output is correct |
4 |
Correct |
4 ms |
620 KB |
Output is correct |
5 |
Correct |
3 ms |
620 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
376 KB |
Output is correct |
2 |
Correct |
3 ms |
488 KB |
Output is correct |
3 |
Correct |
3 ms |
488 KB |
Output is correct |
4 |
Correct |
4 ms |
620 KB |
Output is correct |
5 |
Correct |
3 ms |
620 KB |
Output is correct |
6 |
Correct |
3 ms |
780 KB |
Output is correct |
7 |
Correct |
32 ms |
920 KB |
Output is correct |
8 |
Correct |
13 ms |
920 KB |
Output is correct |
9 |
Correct |
47 ms |
920 KB |
Output is correct |
10 |
Correct |
3 ms |
920 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1079 ms |
20560 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
376 KB |
Output is correct |
2 |
Correct |
3 ms |
488 KB |
Output is correct |
3 |
Correct |
3 ms |
488 KB |
Output is correct |
4 |
Correct |
4 ms |
620 KB |
Output is correct |
5 |
Correct |
3 ms |
620 KB |
Output is correct |
6 |
Correct |
3 ms |
780 KB |
Output is correct |
7 |
Correct |
32 ms |
920 KB |
Output is correct |
8 |
Correct |
13 ms |
920 KB |
Output is correct |
9 |
Correct |
47 ms |
920 KB |
Output is correct |
10 |
Correct |
3 ms |
920 KB |
Output is correct |
11 |
Execution timed out |
1079 ms |
20560 KB |
Time limit exceeded |
12 |
Halted |
0 ms |
0 KB |
- |