Submission #1288542

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288542		WH8	Feast (NOI19_feast)	C++20	100 / 100	283 ms	18336 KiB

feast

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define f first
#define s second
#define pb push_back
#define ld long double
#define pll pair<int, int>
#define MAXN 100002
#define mp make_pair
/*
aliens trick / parameter search
let f(x) be the maximum with x segments.
f(x) is convex. 
let l be a fixed value.
define g(x) = f(x) - l*x, thus f(x) = g(x) + l*x
let the maximum value of g(x) across all x be v(l) 
and v(l) occurs at the rightmost index c(l) [it forms a range]
c is just the largest index such that f(x) - f(x-1) >= l.
thus f(c(l))-f(c(l)-1)=l
now we want to know f(k)-f(k-1)
binary search for the largest l such that c(l) >= k
f(k)-f(k-1)=largest l.
then since we defined f(k)=g(k)+l*k and we know g(k)=g(c(l))=v(l)
thus f(k)=v(l)+l*k
 */
 
int n,k,l;
pll mem[300005][2];
bool vis[300005][2];
vector<int> a;

pll dp(int i, bool last){
	if(vis[i][last])return mem[i][last];
	if(i>=n)return {0,0};
	vis[i][last]=true;
	pll take=dp(i+1,1), dont=dp(i+1,0);
	mem[i][last]=max(
		mp(take.f+a[i]-(last?0:l),take.s+(last?0:1)),
		dont
	);
	return mem[i][last];
}
signed main(){
	
	cin>>n>>k;
	int pos=0,val=0;
	for(int i=0;i<n;i++){
		int cur;
		cin>>cur;
		if(cur==0)continue;
		if(a.empty()){
			a.push_back(cur);
			continue;
		}
		if((cur>0 and a.back()>0) or (cur<0 and a.back()<0)){
			a.back()+=cur;
		}
		else{
			a.push_back(cur);
		}
	}
	n=a.size();
	for(int i=0;i<n;i++){
		if(a[i]>0){
			pos++;
			val+=a[i];
		}
	}
	int hi=1e15, lo=1;	
	if(pos<=k){
		cout<<val;
		return 0;
	}
	pll vc;
	int ansv,ansl;
	while(lo<=hi){
		for(int i=0;i<n;i++) {
			vis[i][0]=vis[i][1]=0;
		}
		l=(lo+hi)/2;
		vc=dp(0,0);
		//~ printf("current lambda %lld, highest value %lld, max seg %lld\n",l,vc.f,vc.s);
		if(vc.s>=k){
			ansv=vc.f;
			ansl=l;
			lo=l+1;
		}
		else{
			hi=l-1;
		}
	}
	cout<<ansv+ansl*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