Submission #1209099

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209099		Boomyday	Remittance (JOI19_remittance)	C++17	55 / 100	1092 ms	12104 KiB

remittance

#include <bits/stdc++.h>
using namespace std;

// Binary exponentiation (long double version)
long double bexp(long double a, int k) {
    if (k == 0) return 1.0L;
    long double half = bexp(a, k / 2);
    long double res = half * half;
    if (k % 2 == 1) res *= a;
    return res;
}

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;
    }

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

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

    long double denom = bexp(2.0L, n) - 1;
    long double raw_ans0 = val / denom;

    // Use tighter epsilon for integer check
    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;
}

• Subtask 1: 15 / 15
• Subtask 2: 40 / 40
• Subtask 3: 0 / 45