Submission #1145570

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145570		hirayuu_oj	Remittance (JOI19_remittance)	C++20	0 / 100	0 ms	328 KiB

remittance

#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0; i<(n); i++)
#define rrep(i,n) for(ll i=(n)-1; i>=0; i--)
#define rng(i,l,r) for(ll i=(l); i<(r); i++)
#define all(x) x.begin(),x.end()
#define fi first
#define se second
using ll=long long;

int main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int N;cin>>N;
    vector<pair<ll,ll>> money(N);
    rep(i,N)cin>>money[i].fi>>money[i].se;
    vector<ll> num(N+60,0);
    rep(i,N){
        ll p=money[(i+1)%N].fi-money[(i+1)%N].se;
        num[i]+=p;
    }
    rep(i,N+59){
        ll carry=num[i]/2;
        if(num[i]<0)carry=-((-num[i]+1)/2);
        num[i]-=carry*2;
        num[i+1]+=carry;
    }
    if(num[N+59]!=0){
        cout<<"No\n";return 0;
    }
    ll send=0;
    rrep(x,61){
        if(num[N+x-1]==1){
            send+=1LL<<x;
            rep(j,N){
                num[x+j]--;
            }
        }
        rep(i,N+59){
            ll carry=num[i]/2;
            if(num[i]<0)carry=-((-num[i]+1)/2);
            num[i]-=carry*2;
            num[i+1]+=carry;
        }
        if(num[N+59]!=0){
            cout<<"No\n";return 0;
        }
    }
    rep(i,N+60){
        if(num[i]!=0){
            cout<<"No\n";
            return 0;
        }
    }
    vector<ll> sends(N);
    sends[0]=send;
    rng(i,1,N){
        if((money[i].fi-money[i].se+sends[i-1])<0){
            cout<<"No\n";
            return 0;
        }
        if((money[i].fi-money[i].se+sends[i-1])%2==1){
            cout<<"No\n";
            return 0;
        }
        sends[i]=(money[i].fi-money[i].se+sends[i-1])/2;
    }
    rep(i,N){
        if(money[i].fi+sends[(i+N-1)%N]-sends[i]*2!=money[i].se){
            cout<<"No\n";return 0;
        }
    }
    rep(i,70){
        rep(j,N){
            ll mx=min(money[j].fi/2,sends[j]);
            sends[j]-=mx;
            money[j].fi-=mx*2;
            money[(j+1)%N].fi+=mx;
        }
    }
    bool flg=false;
    rep(i,N){
        if(sends[i]==0)flg=true;
    }
    if(flg)cout<<"Yes\n";
    else cout<<"No\n";
}

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