Submission #1209933

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209933		cbd_6969	Feast (NOI19_feast)	C++20	100 / 100	155 ms	12148 KiB

feast

#include<iostream>
#include<vector>
using namespace std;

#define int long long

const int N=3e5+5;
int n, k;
int a[N];

pair<int, int> lambda(int el){
	pair<int, int> dp0[n+1], dp1[n+1];
	dp0[0]={0, 0};
	dp1[0]={-1e18, 0};
	for(int i=1; i<=n; i++){
		dp1[i]=max(make_pair(dp0[i-1].first+a[i]-el, dp0[i-1].second+1), make_pair(dp1[i-1].first+a[i], dp1[i-1].second));
		dp0[i]=max(dp1[i], dp0[i-1]);
	}
	
	return max(dp0[n], dp1[n]);
}

int32_t main(){
	cin>>n>>k;
	for(int i=1; i<=n; i++){
		cin>>a[i];
	}
	
	int l=0, r=1e15;
	while(l<r){
		int el=(l+r+1)/2;
		if(lambda(el).second>=k){
			l=el;
		}
		else r=el-1;
	}
	
	cout<<lambda(l).first+l*k;
}

• 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