Advertisement
Guest User

Untitled

a guest
Apr 28th, 2017
54
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.46 KB | None | 0 0
  1.  
  2.  
  3. #include <cstdio>
  4. #include <vector>
  5. #include <algorithm>
  6. #include <iostream>
  7. #include <cstring>
  8. #include "optimization.h"
  9. #include <stack>
  10. #include <string>
  11. #include <stdlib.h>
  12. #include <stdio.h>
  13. #include <vector>
  14. #include <map>
  15. #include <unordered_map>
  16. #include <list>
  17. #include <set>
  18. #include <bits/stdc++.h>
  19.  
  20.  
  21. struct vasyna_korobka{
  22.     int ves;
  23.     int tyasheloves;
  24. };
  25.  
  26. bool proverka(vasyna_korobka& a, vasyna_korobka& b){
  27.     return (a.ves + a.tyasheloves < b.ves + b.tyasheloves);
  28. }
  29.  
  30. int main(){
  31.  
  32.  
  33.  //   freopen("text.in", "r", stdin);
  34.  
  35.     int n;
  36.     n = readInt();
  37.     std::vector<vasyna_korobka> uborka(n);
  38.     for (int i = 0; i < n; ++i){
  39.         uborka[i].ves = readInt();
  40.         uborka[i].tyasheloves = readInt();
  41.     }
  42.     std::sort(uborka.begin(), uborka.end(), proverka);
  43.  
  44.    
  45.     std::priority_queue<int> take;
  46.     int cnt = 1;
  47.     int all = uborka[0].ves;
  48.     int samaya_tyasholaya = uborka[0].ves;
  49.     take.push(all);
  50.     for (int i = 1; i < n; ++i){
  51.         if (all <= uborka[i].tyasheloves){
  52.             cnt++;
  53.             all += uborka[i].ves;
  54.             take.push(uborka[i].ves);
  55.             samaya_tyasholaya = take.top();
  56.         }
  57.         else
  58.         if (samaya_tyasholaya >= uborka[i].ves){
  59.             all = all + uborka[i].ves - samaya_tyasholaya;
  60.             take.pop();
  61.             take.push(uborka[i].ves);
  62.             samaya_tyasholaya = take.top();
  63.         }
  64.     }
  65.  
  66.     writeInt(cnt);
  67. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement