Submission #1070903

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070903		amirhoseinfar1385	Feast (NOI19_feast)	C++17	100 / 100	319 ms	14056 KiB

feast

#include<bits/stdc++.h>
using namespace std;
const long long maxn=300000+10;
long long n,k,all[maxn];

pair<long long ,long long>check(long long mid){
	vector<pair<long long ,long long>>dp0(n),dp1(n);
	pair<long long,long long>ret;
	for(long long i=0;i<n;i++){
		dp1[i]=make_pair(all[i]-mid,1);
		dp0[i]=make_pair(0,0);
		if(i==0){
			continue;
		}
		dp1[i]=max(dp1[i],make_pair(dp0[i-1].first-mid+all[i],dp0[i-1].second+1));
		dp1[i]=max(dp1[i],make_pair(dp1[i-1].first+all[i],dp1[i-1].second));
		dp0[i]=max(dp0[i],dp0[i-1]);
		dp0[i]=max(dp0[i],dp1[i-1]);
	}
	ret.second=max(dp0[n-1],dp1[n-1]).second;
	for(long long i=0;i<n;i++){
		dp1[i]=make_pair(all[i]-mid,-1);
		dp0[i]=make_pair(0,0);
		if(i==0){
			continue;
		}
		dp1[i]=max(dp1[i],make_pair(dp0[i-1].first-mid+all[i],dp0[i-1].second-1));
		dp1[i]=max(dp1[i],make_pair(dp1[i-1].first+all[i],dp1[i-1].second));
		dp0[i]=max(dp0[i],dp0[i-1]);
		dp0[i]=max(dp0[i],dp1[i-1]);
	}
	ret.first=max(dp0[n-1],dp1[n-1]).second*-1;
	return ret;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>k;
	for(long long i=0;i<n;i++){
		cin>>all[i];
	}
	long long opt=0;
	long long high=1e15,low=-1,mid;
	while(high-low>1){
		mid=(high+low)>>1;
		pair<long long ,long long>stf=check(mid);
		if(stf.first<=k&&stf.second>=k){
			opt=mid;
			break;
		}
		if(stf.second<k){
			high=mid;
		}else{
			low=mid;
		}
	}
	mid=opt;
	vector<pair<long long ,long long>>dp0(n),dp1(n);
	pair<long long,long long>ret;
	for(long long i=0;i<n;i++){
		dp1[i]=make_pair(all[i]-mid,1);
		dp0[i]=make_pair(0,0);
		if(i==0){
			continue;
		}
		dp1[i]=max(dp1[i],make_pair(dp0[i-1].first-mid+all[i],dp0[i-1].second+1));
		dp1[i]=max(dp1[i],make_pair(dp1[i-1].first+all[i],dp1[i-1].second));
		dp0[i]=max(dp0[i],dp0[i-1]);
		dp0[i]=max(dp0[i],dp1[i-1]);
	}
	cout<<max(dp1[n-1],dp0[n-1]).first+k*opt<<endl;
	//cout<<mid<<endl;
}

• 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