oj.uz

Submission #63464

# Submission time Handle Problem Language Result Execution time Memory
63464 2018-08-01T21:18:31 Z ksun48 Homecoming (BOI18_homecoming) C++14
31 / 100
 203 ms 47736 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;
	}
	LL best = 0;
	LL bestidx = 0;
	LL sum = 0;
	for(int i = 0; i < k; i++){
		sum += a[i] - b[i];
		if(sum > best){
			best = sum;
			bestidx = i;
		}
	}
	//ans = max(ans, test(n, k, a, b, 0));
	ans = max(ans, test(n, k, a, b, k-1));
	ans = max(ans, test(n, k, a, b, k));
	ans = max(ans, test(n, k, a, b, bestidx));
	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 2 ms 356 KB Output is correct
3 Correct 4 ms 392 KB Output is correct
4 Correct 2 ms 440 KB Output is correct
5 Correct 3 ms 568 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 2 ms 356 KB Output is correct
3 Correct 4 ms 392 KB Output is correct
4 Correct 2 ms 440 KB Output is correct
5 Correct 3 ms 568 KB Output is correct
6 Correct 3 ms 916 KB Output is correct
7 Correct 3 ms 972 KB Output is correct
8 Correct 3 ms 972 KB Output is correct
9 Correct 3 ms 988 KB Output is correct
10 Correct 5 ms 988 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 41296 KB Output is correct
2 Correct 7 ms 41296 KB Output is correct
3 Correct 203 ms 47736 KB Output is correct
4 Correct 10 ms 47736 KB Output is correct
5 Incorrect 40 ms 47736 KB Output isn't correct

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 4 ms 392 KB Output is correct
4 Correct 2 ms 440 KB Output is correct
5 Correct 3 ms 568 KB Output is correct
6 Correct 3 ms 916 KB Output is correct
7 Correct 3 ms 972 KB Output is correct
8 Correct 3 ms 972 KB Output is correct
9 Correct 3 ms 988 KB Output is correct
10 Correct 5 ms 988 KB Output is correct
11 Correct 165 ms 41296 KB Output is correct
12 Correct 7 ms 41296 KB Output is correct
13 Correct 203 ms 47736 KB Output is correct
14 Correct 10 ms 47736 KB Output is correct
15 Incorrect 40 ms 47736 KB Output isn't correct