Submission #677630

#TimeUsernameProblemLanguageResultExecution timeMemory
677630jhwest2Remittance (JOI19_remittance)C++14
100 / 100
254 ms36436 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1010101; const ll INF = 1e13 + 10; int n; ll a[N], b[N]; int main() { cin.tie(0); ios_base::sync_with_stdio(0); cin >> n; bool f = false, g = false; for (int i = 0; i < n; i++) { ll x, y; cin >> x >> y; if (x) f = true; if (y) g = true; a[i] = b[i] = x - y; } if (!g) { if (!f) cout << "Yes"; else cout << "No"; return 0; } ll L = -1, R = 2e9 + 10; while (L < R) { ll M = (L + R) >> 1; for (int i = 0; i < n; i++) a[i] = b[i]; int r = 0; for (int i = n - 1; i > 0; i--) { ll d = M - a[i]; a[i] += d; a[i - 1] -= 2 * d; if (a[i - 1] < -INF) { r = 1; break; } if (a[i - 1] > INF) { r = 2; break; } } if (r == 1) R = M; else if (r == 2) L = M + 1; else { if (a[0] <= M) R = M; else L = M + 1; } } for (int i = 0; i < n; i++) a[i] = b[i]; for (int i = n - 1; i > 0; i--) { ll d = L - a[i]; a[i] += d; a[i - 1] -= 2 * d; if (a[i - 1] < -INF || a[i - 1] > INF) { return !(cout << "No"); } } if (a[0] != L) return !(cout << "No"); for (int i = n - 1; i >= 0; i--) { L = 2 * L - b[i]; if (L < 0) return !(cout << "No"); } cout << "Yes"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...