Submission #1100192

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100192		vjudge1	Feast (NOI19_feast)	C++17	100 / 100	136 ms	15252 KiB

feast

#include<bits/stdc++.h>
using namespace std;
#define ll long long int 
const int N = 3e5 + 5, mod = 1e9 + 7;
ll arr[N];
ll dp[2][N], cnt[2][N];
int32_t main() {
    ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, k; cin >> n >> k;
	for(int i = 1; i <= n; i++) cin >> arr[i];
	ll mn = -1e16;
	ll ans = mn;
	ll lo = mn, hi = -mn;
	while(lo <= hi) {
		ll mi = (lo + hi) / 2;
		dp[1][0] = mn;
		cnt[1][0] = 1;
		for(int i = 1; i <= n; i++) {
			dp[0][i] = max(dp[0][i - 1], dp[1][i - 1]);
			if(dp[0][i - 1] > dp[1][i - 1])
				cnt[0][i] = cnt[0][i - 1];
			else
				cnt[0][i] = cnt[1][i - 1];

			dp[1][i] = max(dp[0][i - 1] - mi, dp[1][i - 1]) + arr[i];
			if(dp[0][i - 1] - mi > dp[1][i - 1]) 
				cnt[1][i] = cnt[0][i - 1] + 1;
			else cnt[1][i] = cnt[1][i - 1];
		}
		int part;
		ll cost;
		if(dp[0][n] >= dp[1][n]) {
			part = cnt[0][n]; 
			cost = dp[0][n] + part * mi;
		}
		else {
			part = cnt[1][n];
			cost = dp[1][n] + part * mi;
		}

		if(part <= k) ans = max(ans, cost), hi = mi - 1;
		else lo = mi + 1; 
	}
	cout << ans << "\n";
	return 0;
}

• 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