Submission #1209100

#TimeUsernameProblemLanguageResultExecution timeMemory
1209100BoomydayRemittance (JOI19_remittance)C++17
55 / 100
458 ms27696 KiB
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> X(n);
    long long sa = 0, sb = 0;

    for (int i = 0; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        sa += a;
        sb += b;
        X[i] = a - b;
    }

    if (sb == 0) {
        if (sa == 0) {
            cout << "Yes\n";
        } else {
            cout << "No\n";
        }
        return 0;
    }

    // Precompute powers of 2 from 0 to n (long double for precision)
    vector<long double> pow2(n + 1);
    pow2[0] = 1.0L;
    for (int i = 1; i <= n; ++i) {
        pow2[i] = pow2[i - 1] * 2.0L;
    }

    vector<long long> ans(n);
    long double val = 0;

    for (int i = 1; i < n; ++i) {
        val += X[i] * pow2[i - 1];
    }
    val += X[0] * pow2[n - 1];

    long double denom = pow2[n] - 1;
    long double raw_ans0 = val / denom;

    constexpr long double EPS = 1e-12L;
    if (fabsl(raw_ans0 - roundl(raw_ans0)) > EPS) {
        cout << "No\n";
        return 0;
    }

    ans[0] = (long long)roundl(raw_ans0);

    if (ans[0] < 0) {
        cout << "No\n";
        return 0;
    }

    for (int i = 1; i < n; ++i) {
        long long sum = ans[i - 1] + X[i];
        if (sum % 2 != 0) {
            cout << "No\n";
            return 0;
        }
        ans[i] = sum / 2;
        if (ans[i] < 0) {
            cout << "No\n";
            return 0;
        }
    }

    cout << "Yes\n";
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...