Advertisement
Guest User

F

a guest
Oct 17th, 2015
453
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.34 KB | None | 0 0
  1. #pragma warning (disable : 4996)
  2. #pragma comment(linker, "/STACK:36777216")
  3.  
  4.  
  5.  
  6. #include <stdlib.h>
  7. #include <iostream>
  8. #include <vector>
  9. #include <string>
  10. #include <assert.h>
  11. #include <stack>
  12. #include <algorithm>
  13. #include <ios>
  14. #include <iostream>
  15. #include <fstream>
  16. #include <iomanip>
  17. #include <queue>
  18. #include <set>
  19. #include <functional>
  20. #include <cmath>
  21. #include <sstream>
  22. #include <map>
  23. #include <memory.h>
  24. #include <stdio.h>
  25. #include <cassert>
  26. #include <string.h>
  27. #include <deque>
  28. #include <ctime>
  29. #include <unordered_map>
  30. #include <list>
  31.  
  32. #define forn(i , n) for (i64 i = 0; i < n; ++i)
  33. #define down(i, n) for (int i = (n) - 1; i >= 0; --i)
  34.  
  35.  
  36. using namespace std;
  37.  
  38. typedef unsigned long long int u64;
  39. typedef long long int i64;
  40. typedef vector<int> vint;
  41. typedef vector<i64> vi64;
  42. typedef pair<int, int> pint;
  43. typedef pair<i64, i64> pi64;
  44.  
  45. #define FILE_NAME "file"
  46. #define CONTEST "seq"
  47. #define M_PI 3.14159265358979323846
  48. #define ALL(a) (a).begin(), (a).end()
  49.  
  50.  
  51. const int inf = 1000000000;
  52.  
  53. #define MOD 1000000007
  54.  
  55.  
  56. #define EPS 10E-10
  57.  
  58. const int N = 2000000;
  59.  
  60.  
  61. struct Event
  62. {
  63.     int a, o, i;
  64.     bool operator<(const Event & b) const
  65.     {
  66.         return a < b.a;
  67.     }
  68. };
  69.  
  70.  
  71. int main()
  72. {
  73.     ios_base::sync_with_stdio(false);
  74.     cin.tie(NULL);
  75.     cout << fixed << setprecision(15);
  76.     srand(16);
  77.     int start = clock();
  78. #ifdef FILE_INPUT
  79.     freopen(FILE_NAME ".in", "r", stdin);
  80.     freopen(FILE_NAME ".out", "w", stdout);
  81. #endif
  82.    
  83.     int n;
  84.     cin >> n;
  85.     vector<pint> arr(n);
  86.     vector<Event> events;
  87.     forn(i, n)
  88.     {
  89.         cin >> arr[i].first >> arr[i].second;
  90.         Event a;
  91.         a.a = arr[i].first;
  92.         a.i = i;
  93.         a.o = 0;
  94.         events.push_back(a);
  95.         a.a = arr[i].second;
  96.         a.o = 1;
  97.         events.push_back(a);
  98.     }
  99.     sort(events.begin(), events.end());
  100.     int l = 0, r = 10000 / n + 1;
  101.     while (r - l > 1)
  102.     {
  103.         int m = (r + l) / 2;
  104.         vector<int> want(n, m);
  105.         set<int> available;
  106.         vector<int> will(n, 0);
  107.         int currE = 0;
  108.         forn(i, 10001)
  109.         {
  110.             while (currE < events.size() && i >= events[currE].a)
  111.             {
  112.                 int j = events[currE].i;
  113.                 if (events[currE].o == 0)
  114.                 {
  115.                     available.insert(j);
  116.                    
  117.                     will[j] = arr[j].second - arr[j].first;
  118.                 }
  119.                 else
  120.                 {
  121.                     available.erase(j);
  122.                 }
  123.                 currE++;
  124.             }
  125.             int bestToEat = -1;
  126.             int res = -1000000000;
  127.             for (auto & j : available)
  128.             {
  129.                 int c = want[j] - will[j];
  130.                 if (want[j] && c > res)
  131.                 {
  132.                     bestToEat = j;
  133.                     res = c;
  134.                 }
  135.                 will[j]--;
  136.             }
  137.             if (bestToEat != -1)
  138.             {
  139.                 want[bestToEat]--;
  140.             }
  141.         }
  142.         bool bad = false;
  143.         forn(i, n)
  144.         {
  145.             if (want[i] > 0)
  146.             {
  147.                 r = m;
  148.                 bad = true;
  149.                 break;
  150.             }
  151.         }
  152.         if (!bad)
  153.         {
  154.             l = m;
  155.         }
  156.     }
  157.  
  158.  
  159.     cout << l * n;
  160.     return 0;
  161. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement