Submission #533533

#	Time	Username	Problem	Language	Result	Execution time	Memory
533533		Kipras	Feast (NOI19_feast)	C++17	30 / 100	136 ms	9140 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];
        //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){
        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{
        sumAll();
        /*
        if(add==0){
            foods.erase(foods.begin());
            negSeg--;
        }
        if(isPositive==0){
            foods.erase(foods.end());
            negSeg--;
        }
        */
    }

    return 0;
}
/*
10 2
54 2 -3 1 1 2 -6 1 5 10
*/

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:47:10: warning: unused variable 'add' [-Wunused-variable]
   47 |     bool add=isPositive;
      |          ^~~

• Subtask 1: 4 / 4
• Subtask 2: 8 / 8
• Subtask 3: 18 / 18
• Subtask 4: 0 / 10
• Subtask 5: 0 / 11
• Subtask 6: 0 / 20
• Subtask 7: 0 / 29