oj.uz

Submission #1097306

# Submission time Handle Problem Language Result Execution time Memory
1097306 2024-10-06T19:28:50 Z vjudge1 Feast (NOI19_feast) C++17
12 / 100
 336 ms 50152 KB 
#include<bits/stdc++.h>
using namespace std;
const int N = 3e5 + 2;
int n, vis[N][2];
long long pan, a[N];
pair<long long, int> mem[N][2];
pair<long long, int> operator + (pair<long long, int> x, pair<long long, int> y) {
	return make_pair(x.first + y.first, x.second + y.second);
}
pair<long long, int> dp(int i, int f) {
	if (i == n) return {0, 0};
	if (vis[i][f]) return mem[i][f];
	vis[i][f] = 1;
	auto &ret = mem[i][f];
	ret = dp(i + 1, 1);
	ret = max(ret, dp(i + 1, 0) + make_pair(-pan * f + a[i], -1 * f));
	return ret;
}
pair<long long, int> get(long long x) {
	pan = x;
	memset(vis, 0, sizeof(vis));
	return dp(0, 1);
}
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int k;
	cin >> n >> k;
	for (int i = 0; i < n; i++) cin >> a[i];
	// auto z = get(1);
	// cout << z.first << endl;
	// cout << z.second << endl;
	long long l = 0, r = 1 << 30, res = 0;
	while (l <= r) {
		long long m = (l + r) / 2;
		auto [x, y] = get(m);
		if (-y <= k) {
			res = x + k * m;
			r = m - 1;
		} else l = m + 1;
	}
	cout << res << '\n';
	return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 45868 KB Output is correct
2 Correct 310 ms 49748 KB Output is correct
3 Correct 312 ms 50152 KB Output is correct
4 Correct 309 ms 49744 KB Output is correct
5 Correct 334 ms 49636 KB Output is correct
6 Correct 303 ms 48840 KB Output is correct
7 Correct 303 ms 48816 KB Output is correct
8 Correct 313 ms 49760 KB Output is correct
9 Correct 324 ms 48720 KB Output is correct
10 Correct 300 ms 49236 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 46320 KB Output is correct
2 Correct 304 ms 47188 KB Output is correct
3 Correct 285 ms 46164 KB Output is correct
4 Correct 303 ms 46648 KB Output is correct
5 Correct 318 ms 48684 KB Output is correct
6 Correct 308 ms 47188 KB Output is correct
7 Correct 312 ms 48340 KB Output is correct
8 Correct 296 ms 49744 KB Output is correct
9 Correct 268 ms 48508 KB Output is correct
10 Correct 273 ms 48208 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 336 ms 46676 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 2652 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 2652 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 2652 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 45868 KB Output is correct
2 Correct 310 ms 49748 KB Output is correct
3 Correct 312 ms 50152 KB Output is correct
4 Correct 309 ms 49744 KB Output is correct
5 Correct 334 ms 49636 KB Output is correct
6 Correct 303 ms 48840 KB Output is correct
7 Correct 303 ms 48816 KB Output is correct
8 Correct 313 ms 49760 KB Output is correct
9 Correct 324 ms 48720 KB Output is correct
10 Correct 300 ms 49236 KB Output is correct
11 Correct 298 ms 46320 KB Output is correct
12 Correct 304 ms 47188 KB Output is correct
13 Correct 285 ms 46164 KB Output is correct
14 Correct 303 ms 46648 KB Output is correct
15 Correct 318 ms 48684 KB Output is correct
16 Correct 308 ms 47188 KB Output is correct
17 Correct 312 ms 48340 KB Output is correct
18 Correct 296 ms 49744 KB Output is correct
19 Correct 268 ms 48508 KB Output is correct
20 Correct 273 ms 48208 KB Output is correct
21 Incorrect 336 ms 46676 KB Output isn't correct
22 Halted 0 ms 0 KB -