oj.uz

Submission #117084

# Submission time Handle Problem Language Result Execution time Memory
117084 2019-06-14T16:41:32 Z Bruteforceman Homecoming (BOI18_homecoming) C++11
100 / 100
 204 ms 102512 KB 
#include "bits/stdc++.h"
#include "homecoming.h"
using namespace std;
const long long inf = 1e17;
long long S[2000010];
long long dp[2][2000010];

long long solve(int N, int K, int *A, int *B) {
	long long all = 0;
	for(int i = 0; i < N; i++) {
		all += A[i] - B[i];
	}
	long long ans = all;

	long long sum = 0;
	for(int i = 0; i < K; i++) {
		sum += B[i];
	}
	for(int i = 0; i < N; i++) {
		S[i] = sum;
		sum += B[(i + K) % N] - B[i];
	}
	dp[0][0] = 0;
	dp[1][0] = -inf;
	for(int j = 1; j < N; j++) {
		int id = j;
		int prev = (id + N - 1) % N;
		dp[0][id] = max(dp[0][prev], dp[1][prev]);
		dp[1][id] = max(dp[0][prev] + A[id] - S[id], dp[1][prev] + A[id] - B[(id + K - 1) % N]);
	}
	ans = max(ans, dp[0][N - 1]);
	ans = max(ans, dp[1][N - 1]);
	
	dp[0][0] = -inf;
	dp[1][0] = A[0] - S[0];
	for(int j = 1; j < N; j++) {
		int id = j;
		int prev = (id + N - 1) % N;
		dp[0][id] = max(dp[0][prev], dp[1][prev]);
		dp[1][id] = max(dp[0][prev] + A[id] - S[id], dp[1][prev] + A[id] - B[(id + K - 1) % N]);
	}
	ans = max(ans, dp[0][N - 1]);

	dp[0][0] = -inf;
	dp[1][0] = A[0] - B[K - 1];
	for(int j = 1; j < N; j++) {
		int id = j;
		int prev = (id + N - 1) % N;
		dp[0][id] = max(dp[0][prev], dp[1][prev]);
		dp[1][id] = max(dp[0][prev] + A[id] - S[id], dp[1][prev] + A[id] - B[(id + K - 1) % N]);
	}	
	ans = max(ans, dp[1][N - 1]);
	return ans;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 3 ms 384 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 15992 KB Output is correct
2 Correct 5 ms 896 KB Output is correct
3 Correct 192 ms 102512 KB Output is correct
4 Correct 5 ms 1280 KB Output is correct
5 Correct 12 ms 3236 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 48 ms 15992 KB Output is correct
12 Correct 5 ms 896 KB Output is correct
13 Correct 192 ms 102512 KB Output is correct
14 Correct 5 ms 1280 KB Output is correct
15 Correct 12 ms 3236 KB Output is correct
16 Correct 193 ms 102364 KB Output is correct
17 Correct 92 ms 26140 KB Output is correct
18 Correct 173 ms 41092 KB Output is correct
19 Correct 153 ms 58968 KB Output is correct
20 Correct 204 ms 85492 KB Output is correct
21 Correct 180 ms 56524 KB Output is correct