제출 #489468

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
489468		8e7	송금 (JOI19_remittance)	C++17	15 / 100	1 ms	332 KiB

remittance

//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;
void debug(){cout << endl;}
template<class T, class ...U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary (T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#define ll long long
#define maxn 1000005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
int a[maxn], b[maxn], c[maxn], ans[maxn];
int main() {
	io
	int n;
	cin >> n;
	if (n > 25) {
		return 0;
	}
	for (int i = 0;i < n;i++) {
		cin >> a[i] >> b[i];	
		c[i] = b[i] - a[i];
	}
	ll sum = c[0], cnt = 0;
	int cur = 2;
	for (int i = 1;i < n;i++) {
		sum += cur * c[i];
		cur *= 2;
	}
	ans[n-1] = (-sum) / (cur - 1);
	for (int i = 0;i < n - 1;i++) {
		ans[i] = (ans[(i+n-1)%n] - c[i]) / 2;
		//debug(i, ans[i]);
	}
	
	for (int i = 0;i < n;i++) {
		cnt += ans[i];
		if (ans[i] < 0) {
			cout << "No\n";
			return 0;
		}
	}
	cur = 0;
	int prv = n-1;
	while (cnt > 0) {
		int dif = min(ans[cur], a[cur]/2);	
		ans[cur] -= dif, a[cur] -= dif*2;
		a[(cur+1)%n] += dif;	
		cnt -= dif;
		if (dif > 0) {
			prv = cur;
		} else if (cur == prv) {
			cout << "No\n";
			return 0;
		}
		cur = (cur + 1) % n;
	}
	for (int i = 0;i < n;i++) {
		if (a[i] != b[i]) {
			cout << "No\n";
			return 0;
		}
	}
	cout << "Yes\n";
	return 0;

}
/*
5
0 0
1 0
2 3
3 3
4 0
*/

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