Submission #698003

#	Time	Username	Problem	Language	Result	Execution time	Memory
698003		bazzagazza	Feast (NOI19_feast)	C++17	30 / 100	136 ms	6788 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 0;
	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(){
	//freopen("inputfeast.txt", "r", stdin);
	//freopen("b.txt", "w", stdout);
	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 or sgn(a[i]==0)) s+=a[i];
		else{sign=-sign; b.push_back(s); s=a[i];}
	}
	b.push_back(s);
	
	//cout << (int)b.size() << " " << k << endl;
	//for(auto x:b) cout << x << " ";
	//cout << endl;
	
	deque <pair <int, int> > negatives;
	int acc=0;
	for(int i=0; i<(int)b.size(); i++){
		if(sgn(b[i])<0) negatives.push_back({b[i], i});
		else acc+=b[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;
	//cout << (int)b.size()-(int)negatives.size() << " " << k << " " << acc << " " << kadane(0, (int)b.size()-1) << endl;
	
	int res=0;
	int sum=0;
	while((int)segments.size()!=k and (not negatives.empty())){
		sum=0;
		for(auto p:segments){
		
			//cout << p.first << " " << p.second << endl;
		
			sum+=kadane(p.first, p.second);
		}
		res=max(res, sum);
		//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();
	}
	sum=0;
	for(auto p:segments){
	
		//cout << p.first << " " << p.second << endl;
	
		sum+=kadane(p.first, p.second);
	}
	res=max(res, sum);
	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