# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
533559 |
2022-03-06T09:55:12 Z |
Kipras |
Feast (NOI19_feast) |
C++17 |
|
153 ms |
9012 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxN = 3e5+10;
ll n, k;
ll a[maxN];
struct food{
ll from, to, val;
bool positive;
};
vector<pair<pair<ll, ll>, ll>> foods;
ll getAll(){
vector<ll> pos;
for(auto i : foods){
if(i.second>=0)pos.push_back(i.second);
}
ll r=0;
for(ll i = 0; i < pos.size(); i++){
r+=pos[i];
}
return r;
}
ll sumAll(){
vector<ll> pos;
for(auto i : foods){
if(i.second>=0)pos.push_back(i.second);
}
sort(pos.begin(), pos.end());
reverse(pos.begin(), pos.end());
ll r=0;
for(ll i = 0; i < pos.size()&&i<k; i++){
//cout<<pos[i]<<endl;
r+=pos[i];
}
return r;
}
int main()
{
//ios_base::sync_with_stdio(0);cin.tie(nullptr);
cin>>n>>k;
for(ll i = 0; i < n; i++){
cin>>a[i];
//cout<<i<<"a"<<endl;
}
ll i = 0, curSum = 0;
bool isPositive=(a[0]>=0);
bool add=isPositive;
ll posSeg=0, negSeg=0;
for(ll j = 0; j < n; j++){
if(isPositive&&a[j]>=0){
curSum+=a[j];
}
if(!isPositive&&a[j]<=0){
curSum+=a[j];
}
if(!isPositive&&a[j]>0){
negSeg++;
foods.push_back({{i, j-1}, curSum});
isPositive=(isPositive==false);
curSum=a[j];
i=j;
}
if(isPositive&&a[j]<0){
posSeg++;
foods.push_back({{i, j-1}, curSum});
isPositive=(isPositive==false);
curSum=a[j];
i=j;
}
}
if(!isPositive){
negSeg++;
foods.push_back({{i, n}, curSum});
}
if(isPositive){
posSeg++;
foods.push_back({{i, n}, curSum});
}
if(posSeg<=k){
cout<<sumAll();
}else if(k==1){
ll r=0, s=0, sMin=0;
for(ll i = 0; i < n; i++){
s+=a[i];
r=max(r, s-sMin);
sMin=min(sMin, s);
}
cout<<r<<endl;
}
else if(k<=n&&n<=80){
ll ans=sumAll();
vector<pair<ll, ll>> v;
for(ll i = 0; i < foods.size()-1; i++){
if(foods[i].second<0&&foods[i+1].second>0&&foods[i-1].second>0)v.push_back({foods[i].second, i});
}
sort(v.begin(), v.end());
ll tAns=getAll();
for(auto i = 0; i < n-k; i++){
tAns-=v[i].first;
}
cout<<max(ans, tAns);
}
return 0;
}
/*
10 2
54 2 -3 1 1 2 -6 1 5 10
*/
Compilation message
feast.cpp: In function 'll getAll()':
feast.cpp:25:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
25 | for(ll i = 0; i < pos.size(); i++){
| ~~^~~~~~~~~~~~
feast.cpp: In function 'll sumAll()':
feast.cpp:39:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | for(ll i = 0; i < pos.size()&&i<k; i++){
| ~~^~~~~~~~~~~~
feast.cpp: In function 'int main()':
feast.cpp:108:25: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
108 | for(ll i = 0; i < foods.size()-1; i++){
| ~~^~~~~~~~~~~~~~~~
feast.cpp:59:10: warning: unused variable 'add' [-Wunused-variable]
59 | bool add=isPositive;
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
129 ms |
2500 KB |
Output is correct |
2 |
Correct |
103 ms |
2532 KB |
Output is correct |
3 |
Correct |
112 ms |
2556 KB |
Output is correct |
4 |
Correct |
120 ms |
2628 KB |
Output is correct |
5 |
Correct |
109 ms |
2596 KB |
Output is correct |
6 |
Correct |
103 ms |
2444 KB |
Output is correct |
7 |
Correct |
101 ms |
2444 KB |
Output is correct |
8 |
Correct |
110 ms |
2580 KB |
Output is correct |
9 |
Correct |
115 ms |
2468 KB |
Output is correct |
10 |
Correct |
120 ms |
2496 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
55 ms |
2468 KB |
Output is correct |
2 |
Correct |
56 ms |
2508 KB |
Output is correct |
3 |
Correct |
56 ms |
2480 KB |
Output is correct |
4 |
Correct |
55 ms |
2480 KB |
Output is correct |
5 |
Correct |
128 ms |
2440 KB |
Output is correct |
6 |
Correct |
76 ms |
2548 KB |
Output is correct |
7 |
Correct |
57 ms |
2612 KB |
Output is correct |
8 |
Correct |
105 ms |
2500 KB |
Output is correct |
9 |
Correct |
105 ms |
2508 KB |
Output is correct |
10 |
Correct |
69 ms |
2604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
131 ms |
8804 KB |
Output is correct |
2 |
Correct |
115 ms |
8768 KB |
Output is correct |
3 |
Correct |
121 ms |
8884 KB |
Output is correct |
4 |
Correct |
123 ms |
8764 KB |
Output is correct |
5 |
Correct |
131 ms |
8900 KB |
Output is correct |
6 |
Correct |
121 ms |
8900 KB |
Output is correct |
7 |
Correct |
119 ms |
8876 KB |
Output is correct |
8 |
Correct |
128 ms |
8892 KB |
Output is correct |
9 |
Correct |
142 ms |
9012 KB |
Output is correct |
10 |
Correct |
153 ms |
8848 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
129 ms |
2500 KB |
Output is correct |
2 |
Correct |
103 ms |
2532 KB |
Output is correct |
3 |
Correct |
112 ms |
2556 KB |
Output is correct |
4 |
Correct |
120 ms |
2628 KB |
Output is correct |
5 |
Correct |
109 ms |
2596 KB |
Output is correct |
6 |
Correct |
103 ms |
2444 KB |
Output is correct |
7 |
Correct |
101 ms |
2444 KB |
Output is correct |
8 |
Correct |
110 ms |
2580 KB |
Output is correct |
9 |
Correct |
115 ms |
2468 KB |
Output is correct |
10 |
Correct |
120 ms |
2496 KB |
Output is correct |
11 |
Correct |
55 ms |
2468 KB |
Output is correct |
12 |
Correct |
56 ms |
2508 KB |
Output is correct |
13 |
Correct |
56 ms |
2480 KB |
Output is correct |
14 |
Correct |
55 ms |
2480 KB |
Output is correct |
15 |
Correct |
128 ms |
2440 KB |
Output is correct |
16 |
Correct |
76 ms |
2548 KB |
Output is correct |
17 |
Correct |
57 ms |
2612 KB |
Output is correct |
18 |
Correct |
105 ms |
2500 KB |
Output is correct |
19 |
Correct |
105 ms |
2508 KB |
Output is correct |
20 |
Correct |
69 ms |
2604 KB |
Output is correct |
21 |
Correct |
131 ms |
8804 KB |
Output is correct |
22 |
Correct |
115 ms |
8768 KB |
Output is correct |
23 |
Correct |
121 ms |
8884 KB |
Output is correct |
24 |
Correct |
123 ms |
8764 KB |
Output is correct |
25 |
Correct |
131 ms |
8900 KB |
Output is correct |
26 |
Correct |
121 ms |
8900 KB |
Output is correct |
27 |
Correct |
119 ms |
8876 KB |
Output is correct |
28 |
Correct |
128 ms |
8892 KB |
Output is correct |
29 |
Correct |
142 ms |
9012 KB |
Output is correct |
30 |
Correct |
153 ms |
8848 KB |
Output is correct |
31 |
Correct |
1 ms |
204 KB |
Output is correct |
32 |
Correct |
0 ms |
204 KB |
Output is correct |
33 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
34 |
Halted |
0 ms |
0 KB |
- |