Submission #1173683

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173683		empaktus	Feast (NOI19_feast)	C++20	100 / 100	185 ms	35656 KiB

feast

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;

mt19937 rng(42);

pair<ll,ll> anslambda(ll lambda,const vector<ll>& v,vector<vector<ll>>& dp,vector<vector<int>>& segs){
	int n=v.size();
	
	
	dp[0][0]=0;
	dp[0][1]=v[0]-lambda;
	segs[0][0]=0;
	segs[0][1]=1;
	
	for(int i=1;i<n;i++){
		//dp[i][0]=max(ld(0),ld(dp[i-1][0]));
		//dp[i][0]=max(ld(dp[i][0]),ld(dp[i-1][1]));
		dp[i][0]=0;
		segs[i][0]=0;
		if(dp[i][0]<dp[i-1][0]){
			dp[i][0]=dp[i-1][0];
			segs[i][0]=segs[i-1][0];
		}
		
		if(dp[i][0]<dp[i-1][1]){
			dp[i][0]=dp[i-1][1];
			segs[i][0]=segs[i-1][1];
		}
		
		//dp[i][1]=max(ld(v[i]),dp[i-1][0]+v[i]-lambda);
		//dp[i][1]=max(ld(dp[i][1]),ld(dp[i-1][1]+v[i]));
		dp[i][1]=v[i]-lambda;
		segs[i][1]=1;
		if(dp[i][1]<dp[i-1][0]+v[i]-lambda){
			dp[i][1]=dp[i-1][0]+v[i]-lambda;
			segs[i][1]=segs[i-1][0]+1;
		}
		if(dp[i][1]<dp[i-1][1]+v[i]){
			dp[i][1]=dp[i-1][1]+v[i];
			segs[i][1]=segs[i-1][1];
		}
	}
	
	if(dp[n-1][0]>dp[n-1][1]){
		return {dp[n-1][0]+segs[n-1][0]*lambda,segs[n-1][0]};
	}else{
		return {dp[n-1][1]+segs[n-1][1]*lambda,segs[n-1][1]};
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	
	
	ll n,k;
	cin>>n>>k;
	vector<vector<ll>>dp(n,vector<ll>(2,0));
	vector<vector<int>>segs(n,vector<int>(2,0));
	
	vector<ll>v(n,0);
	for(int i=0;i<n;i++){
		cin>>v[i];
		//v[i]=rng()%((int)1e+9);
	}
	/*for(ld lambda=0;lambda<10;lambda+=0.1){
		pair<ld,ld>p=anslambda(lambda,v);
		cout<<p.first<<" "<<p.second<<"\n";
	}*/
	//busco el menor lambda con p.second<=k
	ll l=0;
	ll r=1e18;
	
	while(l<r){
		ll mid=l+(r-l)/2;
		pair<ll,ll>p=anslambda(mid,v,dp,segs);
		if(p.second<=k)
			r=mid;
		else
			l=mid+1;
		//cout<<mid<<p.first<<" "<<p.second<<"\n";
	}

	pair<ll,ll>p=anslambda(r,v,dp,segs);
	cout<<ll(round(p.first))<<"\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