oj.uz

Submission #63417

# Submission time Handle Problem Language Result Execution time Memory
63417 2018-08-01T18:27:53 Z ksun48 Homecoming (BOI18_homecoming) C++14
100 / 100
 779 ms 172732 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, 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 3 ms 560 KB Output is correct
4 Correct 2 ms 560 KB Output is correct
5 Correct 2 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 3 ms 560 KB Output is correct
4 Correct 2 ms 560 KB Output is correct
5 Correct 2 ms 560 KB Output is correct
6 Correct 4 ms 916 KB Output is correct
7 Correct 3 ms 952 KB Output is correct
8 Correct 3 ms 952 KB Output is correct
9 Correct 5 ms 968 KB Output is correct
10 Correct 7 ms 968 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 41340 KB Output is correct
2 Correct 8 ms 41340 KB Output is correct
3 Correct 241 ms 47744 KB Output is correct
4 Correct 7 ms 47744 KB Output is correct
5 Correct 26 ms 47744 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 3 ms 560 KB Output is correct
4 Correct 2 ms 560 KB Output is correct
5 Correct 2 ms 560 KB Output is correct
6 Correct 4 ms 916 KB Output is correct
7 Correct 3 ms 952 KB Output is correct
8 Correct 3 ms 952 KB Output is correct
9 Correct 5 ms 968 KB Output is correct
10 Correct 7 ms 968 KB Output is correct
11 Correct 190 ms 41340 KB Output is correct
12 Correct 8 ms 41340 KB Output is correct
13 Correct 241 ms 47744 KB Output is correct
14 Correct 7 ms 47744 KB Output is correct
15 Correct 26 ms 47744 KB Output is correct
16 Correct 779 ms 163576 KB Output is correct
17 Correct 282 ms 163576 KB Output is correct
18 Correct 442 ms 163576 KB Output is correct
19 Correct 625 ms 163576 KB Output is correct
20 Correct 609 ms 172732 KB Output is correct
21 Correct 622 ms 172732 KB Output is correct