Submission #1118100

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118100		Math4Life2020	Remittance (JOI19_remittance)	C++17	100 / 100	267 ms	98888 KiB

remittance

#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
using ui = __int128;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	ll N; cin >> N;
	ui A[N],B[N],D[2*N];
	for (ll i=0;i<N;i++) {
		ll a,b; cin >> a >> b;
		A[i]=a; B[i]=b;
		D[i]=A[i]-B[i];
		D[i+N]=D[i]; //for convenience
	}
	ui f[N]; //how much money does house i send to house i+1
	if (N <= 35) {
		ui sd = 0;
		for (ll i=1;i<=N;i++) {
			sd += (((ui)1)<<(i-1))*D[i];
		}
		ui qt = ((1LL<<N)-1);
		ll asd = sd;
		if (asd<0) {
			asd = -asd;
		}
		if (asd%qt!=(ui)0) {
			cout << "No\n"; exit(0);
		}
		f[0]=(sd/qt);
	} else {
		ui sd = 0;
		for (ll i=1;i<=34;i++) {
			sd += (((ui)1)<<(i-1))*D[i];
		}
		sd = sd%(1LL<<34);
		if (sd<0) {
			sd += (1LL<<34);
		}
		if (sd==0) {
			f[0]=0;
		} else {
			f[0]=(1LL<<34)-sd;
		}
	}
	for (ll i=1;i<N;i++) {
		ll v2 = f[i-1]+D[i];
		if (v2%2!=0 || v2<0) {
			cout << "No\n"; exit(0);
		}
		f[i]=v2/2;
	}
	if ((D[0]+f[N-1])!=2*f[0]) {
		cout << "No\n"; exit(0);
	}
	while(1) {
		bool dfound = 0;
		for (ll i=0;i<N;i++) {
			ll dmax = min(A[i]/2,f[i]);
			if (dmax>0) {
				dfound=1;
				ll j = (i+1)%N;
				A[i]-=2*dmax;
				A[j]+=dmax;
				f[i]-=dmax;
			}
		}
		if (!dfound) {
			break;
		}
	}
	for (ll i=0;i<N;i++) {
		if (A[i]!=B[i]) {
			cout << "No\n"; exit(0);
		}
	}
	cout << "Yes\n"; 
}

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