oj.uz

Submission #533529

# Submission time Handle Problem Language Result Execution time Memory
533529 2022-03-06T08:58:36 Z Kipras Feast (NOI19_feast) C++17
0 / 100
 121 ms 8820 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];
        //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){
        int r=0, s=0, sMin=0;
        for(int i = 0; i < n; i++){
            s+=a[i];
            r=max(r, s-sMin);
            sMin=min(sMin, s);
        }
        cout<<r<<endl;
    }
    else{
        /*
        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

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
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 103 ms 2480 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 2504 KB Output is correct
2 Correct 59 ms 2588 KB Output is correct
3 Correct 57 ms 2532 KB Output is correct
4 Incorrect 65 ms 2572 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 121 ms 8820 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 103 ms 2480 KB Output isn't correct
2 Halted 0 ms 0 KB -