oj.uz

Submission #63462

# Submission time Handle Problem Language Result Execution time Memory
63462 2018-08-01T21:17:29 Z ksun48 Homecoming (BOI18_homecoming) C++14
100 / 100
 816 ms 163640 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));
	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 2 ms 248 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 2 ms 560 KB Output is correct
4 Correct 2 ms 560 KB Output is correct
5 Correct 3 ms 560 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 2 ms 560 KB Output is correct
4 Correct 2 ms 560 KB Output is correct
5 Correct 3 ms 560 KB Output is correct
6 Correct 3 ms 984 KB Output is correct
7 Correct 3 ms 984 KB Output is correct
8 Correct 4 ms 984 KB Output is correct
9 Correct 4 ms 984 KB Output is correct
10 Correct 6 ms 984 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 41336 KB Output is correct
2 Correct 7 ms 41336 KB Output is correct
3 Correct 221 ms 47708 KB Output is correct
4 Correct 7 ms 47708 KB Output is correct
5 Correct 26 ms 47708 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 2 ms 560 KB Output is correct
4 Correct 2 ms 560 KB Output is correct
5 Correct 3 ms 560 KB Output is correct
6 Correct 3 ms 984 KB Output is correct
7 Correct 3 ms 984 KB Output is correct
8 Correct 4 ms 984 KB Output is correct
9 Correct 4 ms 984 KB Output is correct
10 Correct 6 ms 984 KB Output is correct
11 Correct 179 ms 41336 KB Output is correct
12 Correct 7 ms 41336 KB Output is correct
13 Correct 221 ms 47708 KB Output is correct
14 Correct 7 ms 47708 KB Output is correct
15 Correct 26 ms 47708 KB Output is correct
16 Correct 816 ms 163640 KB Output is correct
17 Correct 364 ms 163640 KB Output is correct
18 Correct 488 ms 163640 KB Output is correct
19 Correct 602 ms 163640 KB Output is correct
20 Correct 666 ms 163640 KB Output is correct
21 Correct 658 ms 163640 KB Output is correct