fork(1) download
copy 
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3.  
  4. template <class X>  void printKickStartTemplate(int testCaseNumber, X value) {
  5.     cout << "Case #" << testCaseNumber << ": " << value << endl;
  6. }
  7.  
  8. const int N = 100 + 2;
  9. int t;
  10. int n;
  11. pair<int, int> data[N];
  12.  
  13. int main() {
  14.     ios_base::sync_with_stdio(0);
  15.     cin.tie(0);
  16.     cin >> t;
  17.     for (int T = 1; T <= t; T++) {
  18.         cin >> n;
  19.         long long totalSum = 0;
  20.         long long currMaxSum = 0;
  21.         long long currRem = 0;
  22.         long long maxFound = 0;
  23.         long long maxCurrRem = 0;
  24.         for (int i = 1; i <= n; i++) {
  25.             cin >> data[i].first >> data[i].second;
  26.             totalSum += data[i].first;
  27.         }
  28.         currMaxSum = totalSum;
  29.         maxFound = totalSum;
  30.  
  31.         priority_queue<pair<long long, long long>, vector<pair<long long, long long> >, greater<pair<long long, long long > > > pq;
  32.         long long removedTillNow = 0;
  33.         for (int i = 1; i <= n; i++) {
  34.             if (totalSum - removedTillNow - data[i].first < data[i].second) {
  35.                 //needs to remove;
  36.  
  37.                 removedTillNow += data[i].first;
  38.                 currRem ++;
  39.                 currMaxSum -= data[i].first;
  40.  
  41.                 if (currMaxSum > maxFound) {
  42.                     maxFound = max(maxFound, currMaxSum);
  43.                     maxCurrRem = currRem;
  44.                 }
  45.  
  46.                 while (!pq.empty()) {
  47.                     int u = pq.top().first;
  48.                     int v = pq.top().second;
  49.                     if (u > totalSum - data[v].first - removedTillNow) {
  50.                         //isko bhi remove karo
  51.                         pq.pop();
  52.                         removedTillNow += u;
  53.                         currRem++;
  54.                         currMaxSum -= 2 * u;
  55.                         if (currMaxSum > maxFound) {
  56.                             maxFound = max(maxFound, currMaxSum);
  57.                             maxCurrRem = currRem;
  58.                         }
  59.                     } else break;
  60.                 }
  61.             } else {
  62.                 pq.push({data[i].second, i});
  63.                 currMaxSum += data[i].first;
  64.                 if (currMaxSum > maxFound) {
  65.                     maxFound = max(maxFound, currMaxSum);
  66.                     maxCurrRem = currRem;
  67.                 }
  68.             }
  69.         }
  70.         if (pq.size() > 1) {
  71.             cout << "Case #" << T << ": " << currRem << " " << "INDEFINITELY" << endl;
  72.         } else {
  73.             cout << "Case #" << T << ": " << maxCurrRem << " " << maxFound << endl;
  74.         }
  75.     }
  76. }
Success #stdin #stdout 0s 4396KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/60YHAb
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!