oj.uz

답안 #63460

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
63460 2018-08-01T21:14:37 Z ksun48 Homecoming (BOI18_homecoming) C++14
31 / 100
 219 ms 47984 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, 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 960 KB Output is correct
7 Correct 3 ms 992 KB Output is correct
8 Correct 4 ms 992 KB Output is correct
9 Correct 4 ms 992 KB Output is correct
10 Correct 5 ms 992 KB Output is correct

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 179 ms 41244 KB Output is correct
2 Correct 8 ms 41244 KB Output is correct
3 Correct 219 ms 47984 KB Output is correct
4 Correct 7 ms 47984 KB Output is correct
5 Incorrect 36 ms 47984 KB Output isn't correct

Subtask #4
0 / 38.0

# 결과 실행 시간 메모리 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 960 KB Output is correct
7 Correct 3 ms 992 KB Output is correct
8 Correct 4 ms 992 KB Output is correct
9 Correct 4 ms 992 KB Output is correct
10 Correct 5 ms 992 KB Output is correct
11 Correct 179 ms 41244 KB Output is correct
12 Correct 8 ms 41244 KB Output is correct
13 Correct 219 ms 47984 KB Output is correct
14 Correct 7 ms 47984 KB Output is correct
15 Incorrect 36 ms 47984 KB Output isn't correct