Submission #1017501

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017501		vjudge1	Feast (NOI19_feast)	C++17	100 / 100	134 ms	12124 KiB

feast

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

const int N = 3e5+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: 4 / 4
• Subtask 2: 8 / 8
• Subtask 3: 18 / 18
• Subtask 4: 10 / 10
• Subtask 5: 11 / 11
• Subtask 6: 20 / 20
• Subtask 7: 29 / 29