oj.uz

Submission #533474

# Submission time Handle Problem Language Result Execution time Memory
533474 2022-03-06T06:29:16 Z Kipras Feast (NOI19_feast) C++17
4 / 100
 1000 ms 12276 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;

void 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];
    }
    cout<<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];
    }

    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;
        }
    }
    foods.push_back({{i, n}, curSum});

    if(posSeg<=k){
        sumAll();
    }else{
        if(add==0){
            foods.erase(foods.begin());
        }
        if(isPositive==0){
            foods.erase(foods.end());
        }
        bool changed;
        do{
            changed=0;
            vector<pair<ll, ll>> v;
            for(ll i = 1; i < foods.size(); i+=2){
                v.push_back({i, foods[i].second});
            }
            sort(v.begin(), v.end());
            for(auto i : v){
                if(posSeg==k)break;
                if(foods[i.first-1].second+foods[i.first+1].second+foods[i.first].second>max(foods[i.first+1].second, foods[i.first-1].second)){
                    ll sum = foods[i.first-1].second+foods[i.first+1].second+foods[i.first].second;
                    //cout<<foods[i.first-1].second<<" "<<foods[i.first+1].second<<" "<<foods[i.first].second<<endl;
                    changed=1;
                    posSeg--;
                    foods.erase(foods.begin()+i.first-1);foods.erase(foods.begin()+i.first-1);
                    foods[i.first-1]={{0, 0}, sum};
                    break;
                }
            }
        }while(changed&&posSeg>k);
        sumAll();
    }

    return 0;
}

Compilation message

feast.cpp: In function 'void sumAll()':
feast.cpp:27: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]
   27 |     for(ll i = 0; i < pos.size()&&i<k; i++){
      |                   ~~^~~~~~~~~~~~
feast.cpp: In function 'int main()':
feast.cpp:85:29: 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]
   85 |             for(ll i = 1; i < foods.size(); i+=2){
      |                           ~~^~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 5348 KB Output is correct
2 Correct 32 ms 5468 KB Output is correct
3 Correct 30 ms 5464 KB Output is correct
4 Correct 29 ms 5460 KB Output is correct
5 Correct 30 ms 5360 KB Output is correct
6 Correct 29 ms 5272 KB Output is correct
7 Correct 31 ms 5264 KB Output is correct
8 Correct 30 ms 5416 KB Output is correct
9 Correct 32 ms 5392 KB Output is correct
10 Correct 30 ms 5416 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3652 KB Output is correct
2 Incorrect 22 ms 3724 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1063 ms 12276 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

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

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 5348 KB Output is correct
2 Correct 32 ms 5468 KB Output is correct
3 Correct 30 ms 5464 KB Output is correct
4 Correct 29 ms 5460 KB Output is correct
5 Correct 30 ms 5360 KB Output is correct
6 Correct 29 ms 5272 KB Output is correct
7 Correct 31 ms 5264 KB Output is correct
8 Correct 30 ms 5416 KB Output is correct
9 Correct 32 ms 5392 KB Output is correct
10 Correct 30 ms 5416 KB Output is correct
11 Correct 23 ms 3652 KB Output is correct
12 Incorrect 22 ms 3724 KB Output isn't correct
13 Halted 0 ms 0 KB -