Submission #533474

#	Time	Username	Problem	Language	Result	Execution time	Memory
533474		Kipras	Feast (NOI19_feast)	C++17	4 / 100	1063 ms	12276 KiB

feast

#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 (stderr)

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 / 4
• Subtask 2: 0 / 8
• Subtask 3: 0 / 18
• Subtask 4: 0 / 10
• Subtask 5: 0 / 11
• Subtask 6: 0 / 20
• Subtask 7: 0 / 29