Submission #1209963

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209963		sadthuff	Feast (NOI19_feast)	C++20	100 / 100	184 ms	12148 KiB

feast

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=3*1e5+5;
int n,k,a[maxn];
pair<int,int> solve(int lambda){
	pair<int,int>dp[n][2];
	dp[0][0]={0,0};
	dp[0][1]={a[0]-lambda,1};
	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][1].second));
	}
	return max(dp[n-1][0],dp[n-1][1]);
}
signed main(){
	cin >> n >> k;
	for( int i=0 ; i < n ; ++i){
		cin >> a[i];
	}
	
	int l=0,r=1e18;
	while (l<r){
		
		int mid=(l+r+1)/2;
		if (solve(mid).second >= k){
			l=mid;
		}
		else r=mid-1;
	}
	cout << solve(l).first+k*l;
}

• 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