Submission #697968

#	Time	Username	Problem	Language	Result	Execution time	Memory
697968		bazzagazza	Feast (NOI19_feast)	C++17	30 / 100	134 ms	7952 KiB

feast

//fofat-x 
#include <bits/stdc++.h>
using namespace std;
#define int long long int

vector <int> b;
int sgn(int x){
	if(x<0) return -1;
	return 1;
}

int kadane(int l, int r){
	int best=0;
	int sum=0;
	for(int i=l; i<=r; i++){
		sum=max(b[i], sum+b[i]);
		best=max(best, sum);
	}
	return best;
}

int32_t main(){
	int n,k;
	cin >> n >> k;
	deque <int> a;
	for(int i=0; i<n; i++){
		int dummy;
		cin >> dummy;
		a.push_back(dummy);
	}
	while(a.front()<=0) a.pop_front();
	if(a.empty()){cout << 0 << endl; return 0;}
	while(a.back()<=0) a.pop_back();
	int sign=1;
	int s=0;
	for(int i=0; i<(int)a.size(); i++){
		if(sgn(a[i])==sign) s+=a[i];
		else{sign=-sign; b.push_back(s); s=a[i];}
	}
	b.push_back(s);
	
	//for(auto x:b) cout << x << " ";
	//cout << endl;
	
	deque <pair <int, int> > negatives;
	for(int i=0; i<(int)b.size(); i++){
		if(sgn(b[i])<0) negatives.push_back({b[i], i});
	}
	sort(negatives.begin(), negatives.end());
	map <int, int> segments;
	segments.insert({0, (int)b.size()-1});
	
	//for(auto x:negatives) cout << x.first << " " << x.second << endl;
	
	k=min(k, (int)b.size()-(int)negatives.size());
	while((int)segments.size()!=k){
		
		//for(auto u:segments) cout << u.first << " " << u.second << endl;
		//cout << endl;
		
		auto ind=segments.upper_bound(negatives.front().second);
		--ind;
		int f=(*ind).first;
		int s=(*ind).second;
		segments.erase(ind);
		segments.insert({f, negatives.front().second-1});
		segments.insert({negatives.front().second+1, s});
		negatives.pop_front();
	}
	int res=0;
	for(auto p:segments){
		
		//cout << p.first << " " << p.second << endl;
		
		res+=kadane(p.first, p.second);
	}
	cout << res << endl;
}

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