oj.uz

Submission #533533

# Submission time Handle Problem Language Result Execution time Memory
533533 2022-03-06T09:00:24 Z Kipras Feast (NOI19_feast) C++17
30 / 100
 136 ms 9140 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){
        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

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 131 ms 2536 KB Output is correct
2 Correct 123 ms 2572 KB Output is correct
3 Correct 110 ms 2584 KB Output is correct
4 Correct 105 ms 2500 KB Output is correct
5 Correct 120 ms 2536 KB Output is correct
6 Correct 126 ms 2500 KB Output is correct
7 Correct 105 ms 2468 KB Output is correct
8 Correct 110 ms 2540 KB Output is correct
9 Correct 109 ms 2572 KB Output is correct
10 Correct 109 ms 2560 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 2500 KB Output is correct
2 Correct 56 ms 2548 KB Output is correct
3 Correct 54 ms 2500 KB Output is correct
4 Correct 80 ms 2544 KB Output is correct
5 Correct 117 ms 2652 KB Output is correct
6 Correct 55 ms 2564 KB Output is correct
7 Correct 59 ms 2608 KB Output is correct
8 Correct 115 ms 2540 KB Output is correct
9 Correct 132 ms 2500 KB Output is correct
10 Correct 61 ms 2696 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 8824 KB Output is correct
2 Correct 127 ms 8760 KB Output is correct
3 Correct 136 ms 8816 KB Output is correct
4 Correct 116 ms 8784 KB Output is correct
5 Correct 134 ms 8868 KB Output is correct
6 Correct 128 ms 9056 KB Output is correct
7 Correct 118 ms 8912 KB Output is correct
8 Correct 119 ms 9140 KB Output is correct
9 Correct 127 ms 9140 KB Output is correct
10 Correct 128 ms 8888 KB Output is correct

Subtask #4
0 / 10.0

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

Subtask #5
0 / 11.0

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

Subtask #6
0 / 20.0

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

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 2536 KB Output is correct
2 Correct 123 ms 2572 KB Output is correct
3 Correct 110 ms 2584 KB Output is correct
4 Correct 105 ms 2500 KB Output is correct
5 Correct 120 ms 2536 KB Output is correct
6 Correct 126 ms 2500 KB Output is correct
7 Correct 105 ms 2468 KB Output is correct
8 Correct 110 ms 2540 KB Output is correct
9 Correct 109 ms 2572 KB Output is correct
10 Correct 109 ms 2560 KB Output is correct
11 Correct 54 ms 2500 KB Output is correct
12 Correct 56 ms 2548 KB Output is correct
13 Correct 54 ms 2500 KB Output is correct
14 Correct 80 ms 2544 KB Output is correct
15 Correct 117 ms 2652 KB Output is correct
16 Correct 55 ms 2564 KB Output is correct
17 Correct 59 ms 2608 KB Output is correct
18 Correct 115 ms 2540 KB Output is correct
19 Correct 132 ms 2500 KB Output is correct
20 Correct 61 ms 2696 KB Output is correct
21 Correct 121 ms 8824 KB Output is correct
22 Correct 127 ms 8760 KB Output is correct
23 Correct 136 ms 8816 KB Output is correct
24 Correct 116 ms 8784 KB Output is correct
25 Correct 134 ms 8868 KB Output is correct
26 Correct 128 ms 9056 KB Output is correct
27 Correct 118 ms 8912 KB Output is correct
28 Correct 119 ms 9140 KB Output is correct
29 Correct 127 ms 9140 KB Output is correct
30 Correct 128 ms 8888 KB Output is correct
31 Correct 1 ms 204 KB Output is correct
32 Correct 0 ms 204 KB Output is correct
33 Incorrect 1 ms 300 KB Output isn't correct
34 Halted 0 ms 0 KB -