Submission #231555

#	Time	Username	Problem	Language	Result	Execution time	Memory
231555		cstuart	Remittance (JOI19_remittance)	C++17	100 / 100	291 ms	28664 KiB

remittance

#define USE_MATH_DEFINES 1
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define MOD 998244353ll
#define INF 1000000000000000000ll
#define EPS 1e-9
#define getchar_unlocked _getchar_nolock
#define putchar_unlocked _putchar_nolock

typedef long long         ll;
typedef long double       ld;
typedef pair <ll,ll>      pl;
typedef tuple <ll,ll,ll>  tl;

ll N, A[1000005], B[1000005], bal, afk, pos;
string ans;

int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> N;
	for (ll i = 1; i <= N; i++) cin >> A[i] >> B[i];
	
	bal = 0;
	afk = 0;
	pos = 1;
	
	while (afk <= N) {
		A[pos] += bal;
		if (A[pos] > B[pos]) {
			if (A[pos] % 2 == B[pos] % 2) {
				bal = (A[pos] - B[pos]) / 2;
				A[pos] = B[pos];
			} else if (B[pos] != 0) {
				bal = (A[pos] - B[pos] + 1) / 2;
				A[pos] = B[pos] - 1;
			} else {
				bal = (A[pos] - B[pos] - 1) / 2;
				A[pos] = 1;
			}
		} else bal = 0;
		if (bal > 0) afk = 0;
        else afk++;
		if (pos == N) pos = 1;
		else pos++;
	}
	
	ans = "Yes";
	if (bal != 0) ans = "No";
	for (ll i = 1; i <= N; i++) {
		if (A[i] != B[i]) ans = "No";
	}
	
	cout << ans;
		
    return 0;
}

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