Submission #400166

#	Time	Username	Problem	Language	Result	Execution time	Memory
400166		timmyfeng	Remittance (JOI19_remittance)	C++17	100 / 100	274 ms	52024 KiB

remittance

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

const int N = 1000000;

long long a[N], b[N], c[N], d[N];

long long calc(long long *poly, long long *sum, int n) {
    copy(poly, poly + n, sum);

    long long carry = 0, whole = 0;
    do {
        for (int i = 0; i < n; ++i) {
            sum[i] += carry;
            carry = sum[i] / 2;
            sum[i] %= 2;
        }
        whole += carry;
    } while (carry > 0);

    if (count(sum, sum + n, 1) == n) {
        fill(sum, sum + n, 0);
        ++whole;
    }

    return whole;
}

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

    int n;
    cin >> n;

    for (int i = 0; i < n; ++i) {
        cin >> a[i] >> b[i];
    }

    if (*max_element(b, b + n) == 0 && *max_element(a, a + n) > 0) {
        cout << "No\n";
        exit(0);
    }

    long long flow = calc(a, c, n) - calc(b, d, n);
    if (!equal(c, c + n, d)) {
        cout << "No\n";
        exit(0);
    }

    for (int i = 0; i < n; ++i) {
        flow = (flow + a[i] - b[i]) / 2;
        if (flow < 0) {
            cout << "No\n";
            exit(0);
        }
    }

    cout << "Yes\n";
}

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