Submission #1173187

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173187		empaktus	Feast (NOI19_feast)	C++20	0 / 100	1095 ms	39904 KiB

feast

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

pair<ld,ld> anslambda(ld lambda,vector<ll>& v){
	int n=v.size();
	vector<vector<ld>>dp(n,vector<ld>(2,0));
	vector<vector<int>>segs(n,vector<int>(2,0));
	
	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<ll>v(n,0);
	for(int i=0;i<n;i++){
		cin>>v[i];
	}
	/*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
	ld l=0;
	ld r=1e+18;
	
	while((r-l)>1e-9){
		ld mid=(l+r)/2;
		pair<ld,ld>p=anslambda(mid,v);
		if(p.second<=k){
			r=mid;
		}else{
			l=mid;
		}
		//cout<<p.first<<" "<<p.second<<"\n";
	}
	pair<ld,ld>p=anslambda(r,v);
	cout<<p.first<<"\n";
	return 0;
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 8
• Subtask 3: 0 / 18
• Subtask 4: 0 / 10
• Subtask 5: 0 / 11
• Subtask 6: 0 / 20
• Subtask 7: 0 / 29