oj.uz

Submission #719329

# Submission time Handle Problem Language Result Execution time Memory
719329 2023-04-05T18:29:28 Z rainboy Homecoming (BOI18_homecoming) C++17
100 / 100
 175 ms 86720 KB 
#include "homecoming.h"

#define N	2000000
#define INF	0x3f3f3f3f3f3f3f3fLL

long long max(long long a, long long b) { return a > b ? a : b; }

long long solve(int n, int k, int *aa, int *bb) {
	static long long pp[N * 2];
	int i;
	long long p, ans, x, y;

	for (i = 0, p = 0; i < n * 2; i++)
		pp[i] = p += bb[i % n];
	ans = 0;
	x = y = 0;
	for (i = 0; i < n; i++) {
		long long z = max(x, y - (i == 0 ? 0 : pp[i - 1]));

		ans = max(ans, z + aa[i] - (pp[i + k - 1] - (i == 0 ? 0 : pp[i - 1])));
		x = max(x, z + aa[i] - (pp[i + k - 1] - (i == 0 ? 0 : pp[i - 1])));
		y = max(y, z + aa[i] + (i == 0 ? 0 : pp[i - 1]));
	}
	x = y = -INF;
	for (i = 0; i < n; i++) {
		long long z = max(max(x, y - (i == 0 ? 0 : pp[i - 1])), -pp[i - 1]);

		ans = max(ans, z + aa[i] - (pp[n - 1] - (i == 0 ? 0 : pp[i - 1])));
		x = max(x, z + aa[i] - (pp[i + k - 1] - (i == 0 ? 0 : pp[i - 1])));
		y = max(y, z + aa[i] + (i == 0 ? 0 : pp[i - 1]));
	}
	return ans;
}

Subtask #1
13.0 / 13.0

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

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 480 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 492 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 46 ms 21468 KB Output is correct
2 Correct 4 ms 860 KB Output is correct
3 Correct 163 ms 86720 KB Output is correct
4 Correct 2 ms 1068 KB Output is correct
5 Correct 9 ms 3004 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 480 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 46 ms 21468 KB Output is correct
12 Correct 4 ms 860 KB Output is correct
13 Correct 163 ms 86720 KB Output is correct
14 Correct 2 ms 1068 KB Output is correct
15 Correct 9 ms 3004 KB Output is correct
16 Correct 175 ms 86660 KB Output is correct
17 Correct 75 ms 24028 KB Output is correct
18 Correct 151 ms 40156 KB Output is correct
19 Correct 112 ms 51008 KB Output is correct
20 Correct 115 ms 69852 KB Output is correct
21 Correct 108 ms 48600 KB Output is correct