Advertisement
Guest User

Untitled

a guest
Mar 9th, 2012
168
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.44 KB | None | 0 0
  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cstring>
  4. #include <cassert>
  5. #include <cmath>
  6. #include <algorithm>
  7. #include <string>
  8. #include <vector>
  9. #include <queue>
  10. #include <list>
  11. #include <set>
  12. #include <map>
  13.  
  14. using namespace std;
  15.  
  16. #define eprintf(...) fprintf(stderr, __VA_ARGS__)
  17. #define pb push_back
  18. #define mp make_pair
  19. #define sz(x) ((int)(x).size())
  20. #define TASKNAME "restack"
  21. #ifdef _WIN32
  22. #define LLD "%I64d"
  23. #elif linux
  24. #define LLD "%lld"
  25. #else
  26. #error Invalid OS...
  27. #endif
  28.  
  29. typedef long long ll;
  30. typedef vector<ll> vll;
  31. typedef vector<int> vi;
  32. typedef vector<vi> vvi;
  33. typedef vector<bool> vb;
  34. typedef vector<vb> vvb;
  35. typedef pair<int, int> pii;
  36.  
  37. int n;
  38. vi as;
  39.  
  40. ll calc(ll tn1) {
  41.   ll ans = abs(tn1);
  42.   ll sum = tn1;
  43.   for (int i = 0; i + 1 < n; i++) {
  44.     sum += as[i];
  45.     ans += abs(sum);
  46.   }
  47.   return ans;
  48. }
  49.  
  50. int main() {
  51.   freopen(TASKNAME ".in", "r", stdin);
  52.   freopen(TASKNAME ".out", "w", stdout);
  53.  
  54.   while (scanf("%d", &n) >= 1) {
  55.     as = vi(n);
  56.     for (int i = 0; i < n; i++) {
  57.       int x, y;
  58.       scanf("%d%d", &x, &y);
  59.       as[i] = x - y;
  60.     }
  61.  
  62.     int L = -3e8, R = 3e8;
  63.     while (L + 2 < R) {
  64.       int M1 = (L + R) / 2;
  65.       int M2 = M1 + 1;
  66.  
  67.       ll v1 = calc(M1), v2 = calc(M2);
  68.       if (v1 <= v2) R = M1;
  69.       else L = M2;
  70.     }
  71.  
  72.     ll bans = 9e18;
  73.     for (int i = L; i <= R; i++)
  74.       bans = min(bans, calc(i));
  75.     printf(LLD"\n", bans);
  76.   }
  77.   return 0;
  78. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement