oj.uz

Submission #698003

# Submission time Handle Problem Language Result Execution time Memory
698003 2023-02-11T19:01:39 Z bazzagazza Feast (NOI19_feast) C++17
30 / 100
 136 ms 6788 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())){
		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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 2584 KB Output is correct
2 Correct 112 ms 3968 KB Output is correct
3 Correct 112 ms 4088 KB Output is correct
4 Correct 107 ms 3944 KB Output is correct
5 Correct 113 ms 3952 KB Output is correct
6 Correct 109 ms 3916 KB Output is correct
7 Correct 109 ms 3884 KB Output is correct
8 Correct 109 ms 3928 KB Output is correct
9 Correct 115 ms 3952 KB Output is correct
10 Correct 107 ms 4004 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 2640 KB Output is correct
2 Correct 60 ms 3776 KB Output is correct
3 Correct 58 ms 3896 KB Output is correct
4 Correct 61 ms 3812 KB Output is correct
5 Correct 121 ms 3832 KB Output is correct
6 Correct 62 ms 3688 KB Output is correct
7 Correct 66 ms 3788 KB Output is correct
8 Correct 109 ms 4032 KB Output is correct
9 Correct 109 ms 3864 KB Output is correct
10 Correct 56 ms 3784 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 5092 KB Output is correct
2 Correct 126 ms 6460 KB Output is correct
3 Correct 136 ms 6492 KB Output is correct
4 Correct 130 ms 6432 KB Output is correct
5 Correct 127 ms 6520 KB Output is correct
6 Correct 129 ms 6592 KB Output is correct
7 Correct 128 ms 6624 KB Output is correct
8 Correct 126 ms 6560 KB Output is correct
9 Correct 129 ms 6608 KB Output is correct
10 Correct 131 ms 6788 KB Output is correct

Subtask #4
0 / 10.0

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

Subtask #5
0 / 11.0

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

Subtask #6
0 / 20.0

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

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 2584 KB Output is correct
2 Correct 112 ms 3968 KB Output is correct
3 Correct 112 ms 4088 KB Output is correct
4 Correct 107 ms 3944 KB Output is correct
5 Correct 113 ms 3952 KB Output is correct
6 Correct 109 ms 3916 KB Output is correct
7 Correct 109 ms 3884 KB Output is correct
8 Correct 109 ms 3928 KB Output is correct
9 Correct 115 ms 3952 KB Output is correct
10 Correct 107 ms 4004 KB Output is correct
11 Correct 57 ms 2640 KB Output is correct
12 Correct 60 ms 3776 KB Output is correct
13 Correct 58 ms 3896 KB Output is correct
14 Correct 61 ms 3812 KB Output is correct
15 Correct 121 ms 3832 KB Output is correct
16 Correct 62 ms 3688 KB Output is correct
17 Correct 66 ms 3788 KB Output is correct
18 Correct 109 ms 4032 KB Output is correct
19 Correct 109 ms 3864 KB Output is correct
20 Correct 56 ms 3784 KB Output is correct
21 Correct 121 ms 5092 KB Output is correct
22 Correct 126 ms 6460 KB Output is correct
23 Correct 136 ms 6492 KB Output is correct
24 Correct 130 ms 6432 KB Output is correct
25 Correct 127 ms 6520 KB Output is correct
26 Correct 129 ms 6592 KB Output is correct
27 Correct 128 ms 6624 KB Output is correct
28 Correct 126 ms 6560 KB Output is correct
29 Correct 129 ms 6608 KB Output is correct
30 Correct 131 ms 6788 KB Output is correct
31 Correct 0 ms 212 KB Output is correct
32 Correct 1 ms 212 KB Output is correct
33 Incorrect 1 ms 300 KB Output isn't correct
34 Halted 0 ms 0 KB -