fork download
copy 
  1. //To debug :  g++ -g file.cpp -o code
  2. //to flush output : fflush(stdout) or cout.flush()
  3. //cout<<setprecision(p)<<fixed<<var
  4. //use 1LL<<i to for 64 bit shifting , (ll)2 because by default 2 is ll
  5. //take care of precedence rule of operators 
  6. //do not forget to change the sizes of arrays and value of contants and other things after debugging  
  7.  
  8. #include<bits/stdc++.h>
  9. using namespace std;
  10. #define ll long long
  11. #define rep(i,a,n) for(i=a;i<n;++i)
  12. #define irep(i,n,a) for(i=n;i>a;--i)
  13. #define mod 1000000007
  14. #define pb push_back
  15. #define big 9223372036854775807
  16. #define big1 LONG_MAX
  17. #define big2 ll_MAX
  18. #define big3 1000000000
  19. #define sma1 LONG_MIN
  20. #define sma2 ll_MIN
  21. #define sma3 -1000000000
  22. #define mp make_pair
  23. #define dub double
  24. #define ivec vector<ll>
  25. #define lvec vector<long long>
  26. #define cvec vector<char>
  27. #define svec vector<string>
  28. #define mt make_tuple
  29. #define MOD 998244353
  30. #define ld long double
  31. #define pi acos(-1.0)
  32.  
  33. #define SZ(x)  (ll)(x.size())
  34.  
  35. //comment the below if not required
  36.  
  37. /*
  38.  
  39. #define ss second.second
  40. #define ff first.first
  41. #define f first
  42. #define s second
  43. #define sf second.first
  44. #define fs first.second
  45. */
  46.  
  47. #define IOS std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
  48.  
  49. //cout<<"Case #"<<c<<": "<<ans<<"\n" ;
  50.  
  51. int main()
  52. {
  53.     IOS;
  54.  
  55.     int t,C=0,n,i,j,pt,ft,r,c,cur,rt;
  56.     ll tot,val,ans;
  57.  
  58.  
  59.     cin>>t;
  60.  
  61.     while(t--)
  62.     {
  63.         ++C;
  64.         cout<<"Case #"<<C<<": ";
  65.  
  66.         cin>>n;
  67.  
  68.         pair<int,int> p[n+1];
  69.  
  70.         tot = 0;
  71.         r = 0;
  72.  
  73.         multiset<pair<int,int>> tft ; //fotget time (ft) and toy number
  74.  
  75.         rep(i,1,n+1)
  76.         {
  77.             cin>>pt>>ft;
  78.             p[i]={pt,ft};
  79.             tot += (ll)pt ; //total playing time
  80.             tft.insert({-ft,i});
  81.         }
  82.  
  83.         ans = tot;
  84.  
  85.         bool m[n+1]={0}; //to mark if toy has been removed
  86.  
  87.         rt = 0;
  88.         val = 0;
  89.  
  90.         for(i=1;i<=n;++i)
  91.         {
  92.  
  93.  
  94.             if(!m[i])
  95.             {
  96.                 //if this toy not removed , tot-pt
  97.  
  98.                 if(p[i].second>(tot-(ll)p[i].first))
  99.                 {
  100.                     //remove this toy and all other toys
  101.                     //whose ft > tot-p[i].first-p[other toy playing time]
  102.  
  103.                     tot -= (ll)p[i].first;
  104.  
  105.                     vector<int> rem;
  106.  
  107.                     m[i]=1;
  108.                     rem.pb(i);
  109.                     ++rt;
  110.  
  111.  
  112.                     for(auto u : tft)
  113.                     {
  114.                         int ind = u.second;
  115.  
  116.                         if(!m[ind])
  117.                         {
  118.                             int temp = -u.first;
  119.                             m[ind]=1;
  120.  
  121.                             if(temp>(tot-(ll)p[ind].first))
  122.                             {   
  123.                                 tot -= (ll)p[ind].first;
  124.  
  125.                                 rem.pb(ind);
  126.                                 ++rt;
  127.                                 if(ind<i)
  128.                                 {
  129.                                     val -= (ll)p[ind].first;
  130.                                 }
  131.                             }
  132.                             else
  133.                                 break;
  134.                         }
  135.                     }
  136.  
  137.                     for(auto ind : rem)
  138.                     {
  139.                         auto v = tft.find({-p[ind].second,ind});
  140.                         tft.erase(v);
  141.                     }
  142.  
  143.  
  144.                 }
  145.                 else
  146.                 {
  147.                     val += (ll)p[i].first;
  148.  
  149.                     if((tot+val)>ans)
  150.                     {
  151.                         ans = tot + val;
  152.                         r = rt;
  153.                     }
  154.                 }
  155.  
  156.  
  157.             }
  158.  
  159.  
  160.         }
  161.  
  162.  
  163.         if(SZ(tft))
  164.                 cout<<rt<<" "<<"INDEFINITELY\n";
  165.         else
  166.             cout<<r<<" "<<ans<<"\n";
  167.  
  168.  
  169.  
  170.     }
  171.  
  172.  
  173.  
  174.     return 0;
  175. }
Success #stdin #stdout 0s 4348KB
comments (?)
stdin
copy 
4
1
5 1
2
5 10
10 3
3
30 17
5 10
10 3
3
5 10
5 10
5 11
stdout
copy 
Case #1: 0 5
Case #2: 0 INDEFINITELY
Case #3: 1 INDEFINITELY
Case #4: 0 25
https://ideone.com/uMQ9WG
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!