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.             if(bestans == running_sum + firstround)
  41. 			    min_deletions = min(min_deletions, cur_deletions);
  42. 			else if(bestans < running_sum + firstround)
  43. 			    min_deletions = cur_deletions;
  44. 			bestans = max(bestans, running_sum + firstround);
  45.             cur_deletions++;
  46.             firstround -= e[i];
  47.             while(!good.empty() && good.top().first > firstround){
  48.                 firstround -= e[good.top().second];
  49.                 running_sum -= e[good.top().second];
  50.                 good.pop();
  51.                 cur_deletions++;
  52.             }
  53.         }
  54.     }
  55.     if(bestans == running_sum + firstround)
  56. 	    min_deletions = min(min_deletions, cur_deletions);
  57. 	else if(bestans < running_sum + firstround)
  58. 	    min_deletions = cur_deletions;
  59. 	bestans = max(bestans, running_sum + firstround);
  60.     if(good.size() > 1){
  61.         return {n - good.size(),-1};
  62.     }
  63.     return {min_deletions,bestans};
  64. }
  65. int main(int argc, char const *argv[])
  66. {   
  67.     fastio;
  68.     enable_io();
  69.     int T = 1;
  70.     cin >> T;
  71.     for(int tests = 1; tests <= T; tests++){
  72.         auto ans = solve();   
  73.         string out = (ans.second == -1)? to_string(ans.first) + " INDEFINITELY": to_string(ans.first) + " " + to_string(ans.second); 
  74.         cout << "Case #" << tests << ": " << out << endl;
  75.     }
  76.     return 0;
  77. }
  78.  
Success #stdin #stdout 0s 4352KB
comments (?)
stdin
copy 
1
3
1 100
10 1
3 50
stdout
copy 
Case #1: 1 23
https://ideone.com/qoqaPn
language:
C++14 (gcc 8.3)
created:
3 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!