Submission #489747

#	Time	Username	Problem	Language	Result	Execution time	Memory
489747		AA_Surely	Remittance (JOI19_remittance)	C++14	100 / 100	203 ms	26244 KiB

remittance

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include <bits/stdc++.h>

#define FOR(i,x,n) 	for(int i=x; i<n; i++)
#define F0R(i,n) 	FOR(i,0,n)
#define ROF(i,x,n) 	for(int i=n-1; i>=x; i--)
#define R0F(i,n) 	ROF(i,0,n)

#define WTF 		cout << "WTF" << endl

#define IOS 		ios::sync_with_stdio(false); cin.tie(0); 

using namespace std;
typedef long long 		LL;

const int MAXN = 1e6 + 1;

int n;
LL as[MAXN], bs[MAXN];

int main() {
    IOS;
    cin >> n;
    F0R(i, n) cin >> as[i] >> bs[i];
    
    bool changed = 1;
    while (changed) {
        changed = 0;
        /*
        cout << "NOW: ";
        F0R(i, n) cout << as[i] << ' ';
        cout << endl;
        */

        F0R(i, n - 1) {
            if (as[i] > bs[i]) {
                if ((as[i] & 1) == (bs[i] & 1)) {
                    as[i + 1] += (as[i] - bs[i]) >> 1;
                    as[i] = bs[i];
                    changed = 1;
                }

                else if (bs[i]) {
                    as[i + 1] += ((as[i] - bs[i]) >> 1) + 1;
                    as[i] = bs[i] - 1;
                    changed = 1;
                }

                else {
                    if (as[i] > 1) changed = 1;
                    as[i + 1] += ((as[i] - bs[i]) >> 1);
                    as[i] = bs[i] + 1;
                }
            }
        }

        if (as[n - 1] > bs[n - 1]) {
            if ((as[n - 1] & 1) == (bs[n - 1] & 1)) {
                as[0] += (as[n - 1] - bs[n - 1]) >> 1;
                as[n - 1] = bs[n - 1];
                changed = 1;
            }

            else if (bs[n - 1]) {
                as[0] += ((as[n - 1] - bs[n - 1]) >> 1) + 1;
                as[n - 1] = bs[n - 1] - 1;
                changed = 1;
            }

            else {
                if (as[n - 1] > 1) changed = 1;
                as[0] += ((as[n - 1] - bs[n - 1]) >> 1);
                as[n - 1] = bs[n - 1] + 1;
            }
        }

        if (!changed) break;
    }

    F0R(i, n) if (as[i] != bs[i]) {
        cout << "No";
        return 0;
    }

    cout << "Yes";
    return 0;
}

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