oj.uz

Submission #698001

# Submission time Handle Problem Language Result Execution time Memory
698001 2023-02-11T18:59:10 Z bazzagazza Feast (NOI19_feast) C++17
0 / 100
 128 ms 6852 KB 
//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())){
		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();
	}
	cout << res << endl;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 105 ms 4172 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 57 ms 3724 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 128 ms 6852 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 300 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 300 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 300 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 105 ms 4172 KB Output isn't correct
2 Halted 0 ms 0 KB -