oj.uz

Submission #697967

# Submission time Handle Problem Language Result Execution time Memory
697967 2023-02-11T15:47:18 Z bazzagazza Feast (NOI19_feast) C++17
0 / 100
 237 ms 7944 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 -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
0 / 4.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 237 ms 7944 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 Incorrect 104 ms 2664 KB Output isn't correct
2 Halted 0 ms 0 KB -