Submission #347112

#	Time	Username	Problem	Language	Result	Execution time	Memory
347112		wwdd	Remittance (JOI19_remittance)	C++14	100 / 100	393 ms	52380 KiB

remittance

//this is gross according to all sensibility
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
const ll LIM = 1e12;
vl wa,wb;
int main() {
	ios::sync_with_stdio(0);cin.tie(0);
	ll n;
	cin >> n;
	vl di;
	for(int i=0;i<n;i++) {
		ll a,b;
		cin >> a >> b;
		wa.push_back(a);
		wb.push_back(b);
		di.push_back(a-b);
	}
	ll st = 0,ed = 1e9+10;
	bool poss = false;
	vl go(n,-1);
	while(st <= ed) {
		ll m = (st+ed)/2;
		ll dif = m-di.back();
		go.back() = m;
		for(int i=n-2;i>=0;i--) {
			go[i] = m+dif;
			dif = m-(di[i]-2*dif);
			dif = min(dif,LIM);
			dif = max(dif,-LIM);
		}
		if(dif > 0) {
			ed = m-1;
		} else if(dif < 0) {
			st = m+1;
		} else {
			poss = true;break;
		}
	}
	ll rus = 0;
	ll rube = 0;
	ll rup = 0;
	for(int i=0;i<n;i++) {
		rus += wb[i];
		rube += wa[i];
		rup += go[i];
		if(go[i] < 0) {
			poss = false;
		}
	}
	if((rus == 0) != (rube == 0)) {
		poss = false;
	}
	if(!poss) {
		cout << "No\n";
	} else {
			cout << "Yes\n";
	}
}

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