Submission #683346

#	Time	Username	Problem	Language	Result	Execution time	Memory
683346		tht2005	Remittance (JOI19_remittance)	C++17	55 / 100	242 ms	35496 KiB

remittance

#include <bits/stdc++.h>

using namespace std;

#define N 1000006
int a[N], b[N];
long long X[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    long long S = 0;
    int z_A = 0, z_B = 0;
    for(int i = 1; i <= n; ++i) {
        cin >> a[i] >> b[i];
        if(a[i] == 0) {
            ++z_A;
        }
        if(b[i] == 0) {
            ++z_B;
        }
        S += (long long)(b[i] - a[i]) << (i - 1);
    }
    if(z_A == n && z_B == n) {
        cout << "Yes";
        return 0;
    }
    if(z_A == n || z_B == n) {
        cout << "No";
        return 0;
    }
    if(S % (1 - (1LL << n)) != 0) {
        cout << "No";
        return 0;
    }
    X[n] = S / (1 - (1LL << n));
    if(X[n] < 0) {
        cout << "No";
        return 0;
    }
    X[0] = X[n];
    for(int i = 1; i < n; ++i) {
        long long val = X[i - 1] + a[i] - b[i];
        if(val < 0 || (val & 1)) {
            cout << "No";
            return 0;
        }
        X[i] = val >> 1;
    }
    cout << "Yes";
    return 0;
}

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