oj.uz

Submission #988350

# Submission time Handle Problem Language Result Execution time Memory
988350 2024-05-24T14:26:15 Z vjudge1 Feast (NOI19_feast) C++17
0 / 100
 259 ms 25552 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][0].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;

}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 24828 KB Output is correct
2 Correct 200 ms 25296 KB Output is correct
3 Correct 207 ms 25552 KB Output is correct
4 Correct 197 ms 25168 KB Output is correct
5 Incorrect 184 ms 25268 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

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

Subtask #3
0 / 18.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 11.0

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

Subtask #6
0 / 20.0

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

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 24828 KB Output is correct
2 Correct 200 ms 25296 KB Output is correct
3 Correct 207 ms 25552 KB Output is correct
4 Correct 197 ms 25168 KB Output is correct
5 Incorrect 184 ms 25268 KB Output isn't correct
6 Halted 0 ms 0 KB -