fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define ll long long
  6. #define int long long
  7. #define pb push_back
  8. #define all(x) (x).begin(),(x).end()
  9. #define fi first
  10. #define se second
  11.  
  12. int const MAXN=1e6+10;
  13. int const INF=1e18;
  14.  
  15. void open(){
  16.     ios_base::sync_with_stdio(false);
  17.     cin.tie(NULL); cout.tie(NULL);
  18. //    freopen(TASK".INP","r",stdin);
  19. //    freopen(TASK".OUT","w",stdout);
  20. }
  21.  
  22. bool compareVal(pair<int,int>a,pair<int,int>b){
  23.     return a.fi+a.se>b.fi+b.se;
  24. }
  25.  
  26. int n,q,ans,mx_tmp;
  27. int s[MAXN],e[MAXN];
  28. bool marked[MAXN];
  29.  
  30. signed main(){
  31.     open();
  32.     cin>>n>>q;
  33.  
  34.     multiset<pair<int,int>> sum;
  35.  
  36.     for(int i=1;i<=n;i++){
  37.         cin>>e[i]>>s[i];
  38.         mx_tmp=max(mx_tmp,s[i]);
  39.  
  40.         sum.insert({s[i]+e[i],i});
  41.     }
  42.  
  43.     while(q--){
  44.         pair<int,int> best=*sum.rbegin();
  45.         if(marked[best.se]==false){
  46.             marked[best.se]=true;
  47.             sum.erase(sum.find(best));
  48.             sum.insert({best.fi-e[best.se],best.se});
  49.         }
  50.         else{
  51.             break;
  52.         }
  53.         ans+=best.fi;
  54.     }
  55.  
  56.  
  57.     cout<<ans+mx_tmp*(q+1);
  58.     return 0;
  59. }
Success #stdin #stdout 0s 5340KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/spL4Bj
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!