oj.uz

Submission #533531

# Submission time Handle Problem Language Result Execution time Memory
533531 2022-03-06T08:59:38 Z Kipras Feast (NOI19_feast) C++17
4 / 100
 173 ms 8848 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{
        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

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

# Verdict Execution time Memory Grader output
1 Correct 147 ms 2520 KB Output is correct
2 Correct 173 ms 2580 KB Output is correct
3 Correct 125 ms 2616 KB Output is correct
4 Correct 151 ms 2644 KB Output is correct
5 Correct 123 ms 2576 KB Output is correct
6 Correct 123 ms 2520 KB Output is correct
7 Correct 124 ms 2516 KB Output is correct
8 Correct 143 ms 2588 KB Output is correct
9 Correct 115 ms 2500 KB Output is correct
10 Correct 131 ms 2596 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 2528 KB Output is correct
2 Correct 70 ms 2504 KB Output is correct
3 Correct 75 ms 2540 KB Output is correct
4 Correct 67 ms 2472 KB Output is correct
5 Incorrect 115 ms 2436 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

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

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 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 1 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 1 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 Correct 147 ms 2520 KB Output is correct
2 Correct 173 ms 2580 KB Output is correct
3 Correct 125 ms 2616 KB Output is correct
4 Correct 151 ms 2644 KB Output is correct
5 Correct 123 ms 2576 KB Output is correct
6 Correct 123 ms 2520 KB Output is correct
7 Correct 124 ms 2516 KB Output is correct
8 Correct 143 ms 2588 KB Output is correct
9 Correct 115 ms 2500 KB Output is correct
10 Correct 131 ms 2596 KB Output is correct
11 Correct 69 ms 2528 KB Output is correct
12 Correct 70 ms 2504 KB Output is correct
13 Correct 75 ms 2540 KB Output is correct
14 Correct 67 ms 2472 KB Output is correct
15 Incorrect 115 ms 2436 KB Output isn't correct
16 Halted 0 ms 0 KB -