oj.uz

Submission #697956

# Submission time Handle Problem Language Result Execution time Memory
697956 2023-02-11T15:14:36 Z bazzagazza Feast (NOI19_feast) C++17
0 / 100
 134 ms 5316 KB 
//fofat-x 
#include <bits/stdc++.h>
using namespace std;

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;
}

int 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;;
	while((int)segments.size()!=k){
		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
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 116 ms 5300 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 2660 KB Output is correct
2 Correct 60 ms 2536 KB Output is correct
3 Correct 58 ms 2584 KB Output is correct
4 Runtime error 63 ms 3948 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 134 ms 5316 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 212 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 212 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 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 116 ms 5300 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -