fork download
  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
stdin
1
3
1 100
10 1
3 50
stdout
Case #1: 0 23