Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <cstdlib>
- #include <cstring>
- #include <cassert>
- #include <cmath>
- #include <algorithm>
- #include <string>
- #include <vector>
- #include <queue>
- #include <list>
- #include <set>
- #include <map>
- using namespace std;
- #define eprintf(...) fprintf(stderr, __VA_ARGS__)
- #define pb push_back
- #define mp make_pair
- #define sz(x) ((int)(x).size())
- #define TASKNAME "restack"
- #ifdef _WIN32
- #define LLD "%I64d"
- #elif linux
- #define LLD "%lld"
- #else
- #error Invalid OS...
- #endif
- typedef long long ll;
- typedef vector<ll> vll;
- typedef vector<int> vi;
- typedef vector<vi> vvi;
- typedef vector<bool> vb;
- typedef vector<vb> vvb;
- typedef pair<int, int> pii;
- int n;
- vi as;
- ll calc(ll tn1) {
- ll ans = abs(tn1);
- ll sum = tn1;
- for (int i = 0; i + 1 < n; i++) {
- sum += as[i];
- ans += abs(sum);
- }
- return ans;
- }
- int main() {
- freopen(TASKNAME ".in", "r", stdin);
- freopen(TASKNAME ".out", "w", stdout);
- while (scanf("%d", &n) >= 1) {
- as = vi(n);
- for (int i = 0; i < n; i++) {
- int x, y;
- scanf("%d%d", &x, &y);
- as[i] = x - y;
- }
- int L = -3e8, R = 3e8;
- while (L + 2 < R) {
- int M1 = (L + R) / 2;
- int M2 = M1 + 1;
- ll v1 = calc(M1), v2 = calc(M2);
- if (v1 <= v2) R = M1;
- else L = M2;
- }
- ll bans = 9e18;
- for (int i = L; i <= R; i++)
- bans = min(bans, calc(i));
- printf(LLD"\n", bans);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement