oj.uz

Submission #533560

# Submission time Handle Problem Language Result Execution time Memory
533560 2022-03-06T09:55:33 Z Kipras Feast (NOI19_feast) C++17
30 / 100
 151 ms 8988 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;

ll getAll(){
    vector<ll> pos;
    for(auto i : foods){
        if(i.second>=0)pos.push_back(i.second);
    }
    ll r=0;
    for(ll i = 0; i < pos.size(); i++){
        r+=pos[i];
    }
    return r;
}

ll 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];
    }
    return 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){
        cout<<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{

        ll ans=sumAll();

        vector<pair<ll, ll>> v;
        for(ll i = 0; i < foods.size()-1; i++){
            if(foods[i].second<0&&foods[i+1].second>0&&foods[i-1].second>0)v.push_back({foods[i].second, i});
        }
        sort(v.begin(), v.end());
        ll tAns=getAll();
        for(auto i = 0; i < n-k; i++){
            tAns-=v[i].first;
        }

        cout<<max(ans, tAns);
    }

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

Compilation message

feast.cpp: In function 'll getAll()':
feast.cpp:25: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]
   25 |     for(ll i = 0; i < pos.size(); i++){
      |                   ~~^~~~~~~~~~~~
feast.cpp: In function 'll sumAll()':
feast.cpp:39: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]
   39 |     for(ll i = 0; i < pos.size()&&i<k; i++){
      |                   ~~^~~~~~~~~~~~
feast.cpp: In function 'int main()':
feast.cpp:108:25: 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]
  108 |         for(ll i = 0; i < foods.size()-1; i++){
      |                       ~~^~~~~~~~~~~~~~~~
feast.cpp:59:10: warning: unused variable 'add' [-Wunused-variable]
   59 |     bool add=isPositive;
      |          ^~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 2560 KB Output is correct
2 Correct 120 ms 2612 KB Output is correct
3 Correct 120 ms 2620 KB Output is correct
4 Correct 151 ms 2592 KB Output is correct
5 Correct 111 ms 2488 KB Output is correct
6 Correct 117 ms 2488 KB Output is correct
7 Correct 121 ms 2520 KB Output is correct
8 Correct 117 ms 2496 KB Output is correct
9 Correct 123 ms 2472 KB Output is correct
10 Correct 120 ms 2464 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 2752 KB Output is correct
2 Correct 74 ms 2516 KB Output is correct
3 Correct 68 ms 2500 KB Output is correct
4 Correct 63 ms 2536 KB Output is correct
5 Correct 110 ms 2496 KB Output is correct
6 Correct 75 ms 2516 KB Output is correct
7 Correct 96 ms 2624 KB Output is correct
8 Correct 129 ms 2540 KB Output is correct
9 Correct 117 ms 2436 KB Output is correct
10 Correct 61 ms 2612 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 8852 KB Output is correct
2 Correct 125 ms 8804 KB Output is correct
3 Correct 118 ms 8772 KB Output is correct
4 Correct 136 ms 8824 KB Output is correct
5 Correct 127 ms 8780 KB Output is correct
6 Correct 126 ms 8840 KB Output is correct
7 Correct 127 ms 8840 KB Output is correct
8 Correct 122 ms 8828 KB Output is correct
9 Correct 117 ms 8884 KB Output is correct
10 Correct 124 ms 8988 KB Output is correct

Subtask #4
0 / 10.0

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

Subtask #5
0 / 11.0

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

Subtask #6
0 / 20.0

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

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 2560 KB Output is correct
2 Correct 120 ms 2612 KB Output is correct
3 Correct 120 ms 2620 KB Output is correct
4 Correct 151 ms 2592 KB Output is correct
5 Correct 111 ms 2488 KB Output is correct
6 Correct 117 ms 2488 KB Output is correct
7 Correct 121 ms 2520 KB Output is correct
8 Correct 117 ms 2496 KB Output is correct
9 Correct 123 ms 2472 KB Output is correct
10 Correct 120 ms 2464 KB Output is correct
11 Correct 76 ms 2752 KB Output is correct
12 Correct 74 ms 2516 KB Output is correct
13 Correct 68 ms 2500 KB Output is correct
14 Correct 63 ms 2536 KB Output is correct
15 Correct 110 ms 2496 KB Output is correct
16 Correct 75 ms 2516 KB Output is correct
17 Correct 96 ms 2624 KB Output is correct
18 Correct 129 ms 2540 KB Output is correct
19 Correct 117 ms 2436 KB Output is correct
20 Correct 61 ms 2612 KB Output is correct
21 Correct 134 ms 8852 KB Output is correct
22 Correct 125 ms 8804 KB Output is correct
23 Correct 118 ms 8772 KB Output is correct
24 Correct 136 ms 8824 KB Output is correct
25 Correct 127 ms 8780 KB Output is correct
26 Correct 126 ms 8840 KB Output is correct
27 Correct 127 ms 8840 KB Output is correct
28 Correct 122 ms 8828 KB Output is correct
29 Correct 117 ms 8884 KB Output is correct
30 Correct 124 ms 8988 KB Output is correct
31 Correct 0 ms 204 KB Output is correct
32 Correct 0 ms 204 KB Output is correct
33 Incorrect 0 ms 204 KB Output isn't correct
34 Halted 0 ms 0 KB -