fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define pb push_back
  4. #define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  5. #define wfile freopen("output.txt", "w", stdout)
  6. #define rfile freopen("input.txt", "r", stdin)
  7. typedef long long ll;
  8. typedef pair<int,int> pii;
  9. typedef pair<ll,ll> pll;
  10. typedef vector<int> vi;
  11. typedef vector<vi> vvi;
  12. void enable_io(){
  13.     #ifdef LOCAL_PROJECT
  14.         wfile;
  15.         rfile;
  16.     #endif
  17. }
  18. pair<int,int> solve(){
  19.     int n;
  20.     cin >> n;
  21.     std::vector<int> e(n,0);
  22.     std::vector<int> r(n,0);
  23.     ll firstround = 0;
  24.     ll bestans = -1;
  25.     for (int i = 0; i < n; ++i)
  26.     {
  27.         cin >> e[i] >> r[i];
  28.         firstround += e[i];
  29.     }
  30.     ll running_sum = 0;
  31.     ll min_deletions = 1e9;
  32.     ll cur_deletions = 0;
  33.     priority_queue<pair<int,int>> good;
  34.     for(int i = 0; i < n; i++){
  35.         if(e[i] + r[i] <= firstround){  
  36.             running_sum += e[i];
  37.             good.push({e[i] + r[i],i});
  38.         }
  39.         else{
  40.             bestans = max(bestans, running_sum + firstround);
  41.             if(bestans == running_sum + firstround){
  42.                 min_deletions = min(min_deletions, cur_deletions);
  43.             }
  44.             cur_deletions++;
  45.             firstround -= e[i];
  46.             while(!good.empty() && good.top().first > firstround){
  47.                 firstround -= e[good.top().second];
  48.                 running_sum -= e[good.top().second];
  49.                 good.pop();
  50.                 cur_deletions++;
  51.             }
  52.         }
  53.     }
  54.     bestans = max(bestans, running_sum + firstround);
  55.     if(bestans == running_sum + firstround){
  56.         min_deletions = min(min_deletions, cur_deletions);
  57.     }        
  58.     if(good.size() > 1){
  59.         return {n - good.size(),-1};
  60.     }
  61.     return {min_deletions,bestans};
  62. }
  63. int main(int argc, char const *argv[])
  64. {   
  65.     fastio;
  66.     enable_io();
  67.     int T = 1;
  68.     cin >> T;
  69.     for(int tests = 1; tests <= T; tests++){
  70.         auto ans = solve();   
  71.         string out = (ans.second == -1)? to_string(ans.first) + " INDEFINITELY": to_string(ans.first) + " " + to_string(ans.second); 
  72.         cout << "Case #" << tests << ": " << out << endl;
  73.     }
  74.     return 0;
  75. }
  76.  
Success #stdin #stdout 0s 4384KB
comments (?)
stdin
copy 
1
3
1 100
10 1
3 50
stdout
copy 
Case #1: 0 23
https://ideone.com/fM5SUU
language:
C++14 (gcc 8.3)
created:
4 years 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!