Submission #533529

#TimeUsernameProblemLanguageResultExecution timeMemory
533529KiprasFeast (NOI19_feast)C++17
0 / 100
121 ms8820 KiB
#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 (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;
      |          ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...