Submission #489542

#	Time	Username	Problem	Language	Result	Execution time	Memory
489542		yungyao	Remittance (JOI19_remittance)	C++17	100 / 100	235 ms	8220 KiB

remittance

using namespace std;
#pragma GCC optimize ("Ofast")
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
#include <stack>
#include <set>
#include <map>

typedef long long LL;
typedef pair<int,int> pii;
#define iter(x) x.begin(),x.end()
#define pb push_back
#define mkp make_pair
#define F first
#define S second
#define REP(n) for (int __=n;__--;)
#define REP0(i,n) for (int i=0;i<n;++i)
#define REP1(i,n) for (int i=1;i<=n;++i)

const int maxn = 1e6+10,mod = 0;
const LL inf = 0;

int a[maxn],b[maxn],n;

bool done(){
    REP1(i,n) if (a[i]) return false;
    return true;
}

bool pos(){
    REP1(i,n) if (a[i] > 1) return true;
    return false;
}

void solve(){
    cin >> n;
    REP1(i,n){
        cin >> a[i] >> b[i];
        a[i] -= b[i];
    }

    while (!done()){
        //REP1(i,n) cerr << a[i] <<' '; cerr << '\n';
        if (!pos()){
            bool ok = true,ok2 = false;
            REP1(i,n) ok &= a[i] == 1, ok2 |= b[i];
            cout << (ok and ok2 ? "Yes\n" : "No\n");
            return;
        }
        for (int i=1;i<n;++i){
            if (a[i] > 1){
                a[i+1] += a[i] >> 1;
                a[i] = a[i] & 1;
            }
        }
        if (a[n] > 1){
            a[1] += a[n] >> 1;
            a[n] = a[n] & 1;
        }
        //REP1(i,n) cerr << a[i] <<' '; cerr << '\n';
    }
    cout << "Yes\n";
}

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

    return 0;
}

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