oj.uz

Submission #861524

# Submission time Handle Problem Language Result Execution time Memory
861524 2023-10-16T12:37:07 Z maks007 Homecoming (BOI18_homecoming) C++14
100 / 100
 128 ms 95944 KB 
#include "bits/stdc++.h"
#include "homecoming.h"

using namespace std;

#define intl long long

intl solve(int n, int k, int *A, int *B) {
	vector <intl> a, b, pref(n);
	function <intl(intl)> get=[&](intl l) {
		intl r = l + k - 1;
		if(r < n) return pref[r] - (l?pref[l-1]:0LL);
		r %= n;
		return pref[r] + (pref[n-1] - (l?pref[l-1]:0LL));
	};
	for(int i = 0; i < n; i ++) a.push_back(A[i]);
	for(int i = 0; i < n; i ++) b.push_back(B[i]);
	for(int i = 0; i < n; i ++) {
		if(i) pref[i] = pref[i-1];
		pref[i] += b[i];
	}
	intl dp[n][2];
	for(int i = 0; i < n; i ++) {
		for(int j = 0; j < n; j ++) dp[i][j] = -1e18;
	}
	dp[0][1] = a[0] - pref[k-1];
	for(int i = 1; i < n; i ++) {
		dp[i][0] = max(dp[i-1][1], dp[i-1][0]);
		dp[i][1] = max(dp[i-1][1] + a[i] - (i + k - 1 < n ? b[i+k-1] : 0LL),
				       dp[i-1][0] + a[i] - (pref[min(n-1,i+k-1)] - (i ? pref[i-1] : 0LL)));
	}
	intl ans = max(dp[n-1][1], dp[n-1][0]);
	for(int i = 0; i < n; i ++) {
		for(int j = 0; j < n; j ++) dp[i][j] = -1e18;
	}
	dp[0][0] = 0;
	for(int i = 1; i < n; i ++) {
		dp[i][0] = max(dp[i-1][1], dp[i-1][0]);
		dp[i][1] = max(dp[i-1][1] + a[i] - b[(i + k - 1) % n], dp[i-1][0] + a[i] - get(i));
	}
	ans = max({ans, dp[n-1][0], dp[n-1][1]});
	return ans;
}

Subtask #1
13.0 / 13.0

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

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 856 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 348 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 23888 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 128 ms 95944 KB Output is correct
4 Correct 1 ms 1372 KB Output is correct
5 Correct 6 ms 1428 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 856 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 32 ms 23888 KB Output is correct
12 Correct 2 ms 348 KB Output is correct
13 Correct 128 ms 95944 KB Output is correct
14 Correct 1 ms 1372 KB Output is correct
15 Correct 6 ms 1428 KB Output is correct
16 Correct 126 ms 94512 KB Output is correct
17 Correct 61 ms 14076 KB Output is correct
18 Correct 101 ms 6504 KB Output is correct
19 Correct 94 ms 55612 KB Output is correct
20 Correct 95 ms 95468 KB Output is correct
21 Correct 92 ms 47452 KB Output is correct