Submission #901376

#	Time	Username	Problem	Language	Result	Execution time	Memory
901376		pcc	Feast (NOI19_feast)	C++17	100 / 100	118 ms	12896 KiB

feast

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>


const ll inf = 1e13;
const int mxn = 3e5+10;
ll arr[mxn];
ll pref[mxn];
pll dp[mxn];
ll N,K;

inline pll calc(ll p){
	pll pt = make_pair(0,0);
	for(int i = 1;i<=N;i++){
		dp[i] = dp[i-1];
		dp[i] = max(dp[i],make_pair(pref[i]+pt.fs-p,pt.sc+1));
		pt = max(pt,make_pair(dp[i].fs-pref[i],dp[i].sc));
	}
	return dp[N];
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>K;
	for(int i = 1;i<=N;i++){
		cin>>arr[i];
		pref[i] = arr[i]+pref[i-1];
	}
	ll l = -inf,r = inf;
	while(l != r){
		ll mid = l+(r-l+1)/2;
		if(calc(mid).sc>=K)l = mid;
		else r = mid-1;
	}
	auto re = calc(l);
	ll ans = re.fs+l*K;
	re = calc(0);
	if(re.sc<=K)ans = max(ans,re.fs);
	cout<<ans;
}

• 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