Submission #1017500

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1017500	2024-07-09T08:28:16 Z	vjudge1	Feast (NOI19_feast)	C++17	41 / 100	19 ms	1884 KB

feast

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define mp make_pair
using namespace std;

const int N = 2e5+1;

int n, k;
ll a[N];

pair<ll, int> dp[N][2];
pair<ll, int> solve(ll lambda) {
	dp[0][1] = {-lambda,1};
	dp[0][0] = {0,0};
	for (int i = 1; i <= n; i++) {
		dp[i][1] = max(
			mp(dp[i-1][1].first+a[i], dp[i-1][1].second),
			mp(dp[i-1][0].first+a[i]-lambda, dp[i-1][0].second+1)
		);
		dp[i][0] = max(dp[i-1][0], dp[i-1][1]);	
	}
	return max(dp[n][0], dp[n][1]);
}

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin >> n >> k;
	for (int i = 1; i <= n; cin >> a[i++]);
	ll l = 1, r = 1e18;
	while (l < r) {
		const ll mid = (l+r)/2;
		if (solve(mid).second > k)
			l = mid+1;
		else
			r = mid;
	}
	cout << solve(l).first + l*solve(l).second;
}

Subtask #1

0 / 4.0

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

Subtask #2

0 / 8.0

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

Subtask #3

0 / 18.0

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

Subtask #4

10.0 / 10.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	1 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct

Subtask #5

11.0 / 11.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	1 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	1 ms	344 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	436 KB	Output is correct
18	Correct	1 ms	348 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Correct	0 ms	348 KB	Output is correct

Subtask #6

20.0 / 20.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	1 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	344 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	1 ms	344 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	436 KB	Output is correct
18	Correct	1 ms	348 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Correct	0 ms	348 KB	Output is correct
21	Correct	1 ms	348 KB	Output is correct
22	Correct	1 ms	348 KB	Output is correct
23	Correct	1 ms	348 KB	Output is correct
24	Correct	1 ms	348 KB	Output is correct
25	Correct	1 ms	348 KB	Output is correct
26	Correct	1 ms	344 KB	Output is correct
27	Correct	1 ms	348 KB	Output is correct
28	Correct	1 ms	348 KB	Output is correct
29	Correct	1 ms	348 KB	Output is correct
30	Correct	1 ms	348 KB	Output is correct

Subtask #7

0 / 29.0

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