Submission #1209976

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209976		nguyendinhbach	Feast (NOI19_feast)	C++17	100 / 100	138 ms	12168 KiB

feast

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define siz(x) (int)(x.size())
#define all(x) x.begin(), x.end()
#define debug_arr(x,len) for(int _=1; _<=len; _++) cout<<x[_]<<" "; cout<<'\n';
#define debug(x) cout<<'\n'<<#x<<": "<<x<<'\n';
const int maxN = 3e5+5;

int n, k, a[maxN];
pair<int,int>cal(int lambda)
{
	pair<int,int>dp[n+5][2];
	dp[1][0] = {0, 0};
	dp[1][1] = {a[1] - lambda, 1};
	for(int i=2; i<=n; i+=1)
	{
		dp[i][0] = max(dp[i-1][0], dp[i-1][1]);
		pair<int,int>tmp1 = {dp[i-1][0].fi + a[i] - lambda, dp[i-1][0].se+1};
		pair<int,int>tmp2 = {dp[i-1][1].fi + a[i], dp[i-1][1].se};
		dp[i][1] = max(tmp1, tmp2);
	}
	return max(dp[n][0], dp[n][1]);
}

int32_t main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin>>n>>k;
	for(int i=1; i<=n; i+=1) cin>>a[i];
	int l = 0, r = 1e18, t = 0;
	while(r - l >= 0)
	{
		int mid = (l+r)>>1;
		if(cal(mid).se >= k) l = mid+1, t = mid;
		else r = mid-1;
	}
	cout<<cal(t).fi+t*k<<'\n';
}

• 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