oj.uz

Submission #63413

# Submission time Handle Problem Language Result Execution time Memory
63413 2018-08-01T18:19:23 Z ksun48 Homecoming (BOI18_homecoming) C++14
62 / 100
 1000 ms 163656 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const LL reallybad = -10000000000000000LL;

LL test(int n, int k, vector<LL> a, vector<LL> b, int x){
	LL ans = reallybad;
	vector<LL> newa;
	vector<LL> newb;
	vector<LL> bpsums(1,0);
	for(int i = 0; i < n; i++){
		newa.push_back(a[(i+x) % n]);
		newb.push_back(b[(i+x) % n]);
	}
	for(int i = 0; i < n; i++){
		bpsums.push_back(bpsums[i] + newb[i]);
	}
	for(int y = 0; y < 2; y++){
		vector<LL> dp0(n+1, reallybad);
		vector<LL> dp1(n+1, reallybad);
		if(y == 0) dp0[0] = 0;
		if(y == 1) dp1[0] = 0;

		for(int i = 0; i <= n; i++){
			dp1[i] = max(dp1[i], dp0[i]);
			if(i + 1 <= n){
				dp0[i+1] = max(dp0[i+1], dp0[i]);
				dp1[i+1] = max(dp1[i+1], dp1[i] + newa[i] - newb[i]);
			}
			if(i + k <= n){
				dp0[i+k] = max(dp0[i+k], dp1[i] - bpsums[i+k] + bpsums[i]);
			}
		}

		if(y == 0) ans = max(ans, dp0[n]);
		if(y == 1) ans = max(ans, dp1[n]);
	}
	return ans;
}

long long solve(int N, int K, int *A, int *B){
	int n = N;
	int k = K;
	k--;
	vector<LL> a, b;
	for(int i = 0; i < n; i++){
		a.push_back(A[i]);
		b.push_back(B[i]);
	}
	LL ans = 0;
	if(k == 0){
		for(int i = 0; i < n; i++){
			if(a[i] >= b[i]){
				ans += a[i] - b[i];
			}
		}
		return ans;
	}
	for(int i = 0; i < k; i++){
		ans = max(ans, test(n, k, a, b, i));
	}
	return ans;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 9 ms 484 KB Output is correct
3 Correct 3 ms 560 KB Output is correct
4 Correct 4 ms 560 KB Output is correct
5 Correct 5 ms 668 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 9 ms 484 KB Output is correct
3 Correct 3 ms 560 KB Output is correct
4 Correct 4 ms 560 KB Output is correct
5 Correct 5 ms 668 KB Output is correct
6 Correct 990 ms 1196 KB Output is correct
7 Correct 797 ms 1352 KB Output is correct
8 Correct 94 ms 1352 KB Output is correct
9 Correct 24 ms 1352 KB Output is correct
10 Correct 5 ms 1352 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 41268 KB Output is correct
2 Correct 60 ms 41268 KB Output is correct
3 Correct 194 ms 47748 KB Output is correct
4 Correct 88 ms 47748 KB Output is correct
5 Correct 87 ms 47748 KB Output is correct

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 9 ms 484 KB Output is correct
3 Correct 3 ms 560 KB Output is correct
4 Correct 4 ms 560 KB Output is correct
5 Correct 5 ms 668 KB Output is correct
6 Correct 990 ms 1196 KB Output is correct
7 Correct 797 ms 1352 KB Output is correct
8 Correct 94 ms 1352 KB Output is correct
9 Correct 24 ms 1352 KB Output is correct
10 Correct 5 ms 1352 KB Output is correct
11 Correct 151 ms 41268 KB Output is correct
12 Correct 60 ms 41268 KB Output is correct
13 Correct 194 ms 47748 KB Output is correct
14 Correct 88 ms 47748 KB Output is correct
15 Correct 87 ms 47748 KB Output is correct
16 Execution timed out 1094 ms 163656 KB Time limit exceeded
17 Halted 0 ms 0 KB -