oj.uz

Submission #988352

# Submission time Handle Problem Language Result Execution time Memory
988352 2024-05-24T14:30:02 Z vjudge1 Feast (NOI19_feast) C++17
12 / 100
 215 ms 25684 KB 
#include <iostream>
#include <vector>
#include <climits>

using namespace std;

int n, k;
vector<int> a;
vector<vector<pair<long long, long long> > > DP;

pair<long long, long long> dp(long long lambda)
{
	DP[0][0] = { 0, 0 };
	for (int i = 1; i <= n; i++)
	{
		DP[i][0] = max(DP[i - 1][0], DP[i - 1][1]);
		DP[i][1] = max( 
			make_pair(DP[i-1][0].first + a[i] - lambda, DP[i-1][0].second + 1), 
			make_pair(DP[i - 1][1].first + a[i], DP[i - 1][1].second)
		);
	}
	return max(DP[n][0], DP[n][1]);
}

int main()
{
	cin >> n >> k;
	DP.resize(n + 1, vector<pair<long long, long long>>(2, { LLONG_MIN, 0 }));
	a.resize(n + 1);
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
	}

	long long l = 0, r = 3e14, lambda;
	while ( r - l > 1)
	{
		lambda = (l + r) / 2;
		auto m = dp(lambda);
		if (m.second > k) l = lambda;
		else r = lambda;
	}
	auto megoldas = dp(r);
	cout << megoldas.first + megoldas.second * r;

	return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 22032 KB Output is correct
2 Correct 192 ms 22364 KB Output is correct
3 Correct 188 ms 22616 KB Output is correct
4 Correct 215 ms 22524 KB Output is correct
5 Correct 185 ms 22360 KB Output is correct
6 Correct 185 ms 24728 KB Output is correct
7 Correct 184 ms 24728 KB Output is correct
8 Correct 177 ms 25168 KB Output is correct
9 Correct 172 ms 24904 KB Output is correct
10 Correct 188 ms 24928 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 22104 KB Output is correct
2 Correct 158 ms 23636 KB Output is correct
3 Correct 146 ms 23268 KB Output is correct
4 Correct 139 ms 23360 KB Output is correct
5 Correct 188 ms 24656 KB Output is correct
6 Correct 153 ms 23040 KB Output is correct
7 Correct 150 ms 23636 KB Output is correct
8 Correct 201 ms 25684 KB Output is correct
9 Correct 181 ms 24660 KB Output is correct
10 Correct 154 ms 23704 KB Output is correct

Subtask #3
0 / 18.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 11.0

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

Subtask #6
0 / 20.0

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

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 22032 KB Output is correct
2 Correct 192 ms 22364 KB Output is correct
3 Correct 188 ms 22616 KB Output is correct
4 Correct 215 ms 22524 KB Output is correct
5 Correct 185 ms 22360 KB Output is correct
6 Correct 185 ms 24728 KB Output is correct
7 Correct 184 ms 24728 KB Output is correct
8 Correct 177 ms 25168 KB Output is correct
9 Correct 172 ms 24904 KB Output is correct
10 Correct 188 ms 24928 KB Output is correct
11 Correct 154 ms 22104 KB Output is correct
12 Correct 158 ms 23636 KB Output is correct
13 Correct 146 ms 23268 KB Output is correct
14 Correct 139 ms 23360 KB Output is correct
15 Correct 188 ms 24656 KB Output is correct
16 Correct 153 ms 23040 KB Output is correct
17 Correct 150 ms 23636 KB Output is correct
18 Correct 201 ms 25684 KB Output is correct
19 Correct 181 ms 24660 KB Output is correct
20 Correct 154 ms 23704 KB Output is correct
21 Incorrect 193 ms 22480 KB Output isn't correct
22 Halted 0 ms 0 KB -