fork download
copy 
  1. #include <algorithm>
  2. #include <fstream>
  3. using namespace std;
  4.  
  5. ifstream F("pitici3.in");
  6. ofstream G("pitici3.out");
  7.  
  8. const int Nmax = 2010;
  9.  
  10. int N,H[Nmax],L[Nmax],oH[Nmax],oHL[Nmax];
  11. int rev[Nmax],l[Nmax],D,h_init,co;
  12.  
  13. bool cmp1(int a,int b)
  14. {
  15.     return H[a] == H[b] ? L[a] < L[b] : H[a] < H[b];
  16. }
  17.  
  18. bool cmp2(int a,int b)
  19. {
  20.     return H[a]+L[a] < H[b]+L[b];
  21. }
  22.  
  23. bool good(int pitic)
  24. {
  25.     int h_now = h_init - H[pitic];
  26.     l[ rev[pitic] ] = 1;
  27.     for (int i=N;i>=0;--i)
  28.         if ( l[i] == 1 )
  29.         {
  30.             if ( h_now + H[oHL[i]] + L[oHL[i]] >= D )
  31.                 h_now += H[oHL[i]];
  32.             else
  33.                 return 0;
  34.         }
  35.     return 1;
  36. }
  37.  
  38. int main()
  39. {
  40.     F>>N;
  41.     for (int i=1;i<=N;++i)
  42.     {
  43.         F>>H[i]>>L[i];
  44.         oH[i] = i;
  45.         oHL[i] = i;
  46.     }
  47.     F>>D;
  48.     sort(oH+1,oH+N+1,cmp1);
  49.     sort(oHL+1,oHL+N+1,cmp2);
  50.     for (int i=1;i<=N;++i)
  51.     {
  52.         rev[oHL[i]] = i;
  53.         h_init += H[i];
  54.     }
  55.     for (int i=1;i<=N;++i)
  56.     {
  57.         int pitic = oH[i];
  58.         if ( good(pitic) )
  59.         {
  60.             l[ rev[pitic] ] = 1;
  61.             h_init -= H[pitic];
  62.             co++;
  63.         }
  64.         else
  65.             l[ rev[pitic] ] = 0;
  66.     }
  67.     G<<co<<'\n';
  68. }
Success #stdin #stdout 0s 3476KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ukUuac
language:
C++ (gcc 8.3)
created:
10 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!