Submission #211768

#	Time	Username	Problem	Language	Result	Execution time	Memory
211768		tselmegkh	Remittance (JOI19_remittance)	C++14	100 / 100	490 ms	28792 KiB

remittance

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 1e6 + 5, inf = 1e9;
#define pb push_back
#define mp make_pair
#define ll long long
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

bool solve(int idx, vi &m, vi &l){
	int cnt = 0, n = m.size();
	for(int i = idx;; i++){
		if(i >= n)i -= n;
		if(i == idx){
			cnt++;
			if(cnt == 50)break;
		}
		if(m[i] > l[i]){
			int x = (m[i] - l[i]) / 2;
			m[(i + 1) % n] += x;
			m[i] -= (2 * x);
			if((m[i] - l[i]) % 2 == 1){
				if(m[i] >= 2){
					m[i] -= 2;
					m[(i + 1) % n] += 1;
				}
			}
		}
	}
	for(int i = 0; i < n; i++){
		if(m[i] != l[i])return 0;
	}
	return 1;
}
int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int n;
	cin >> n;
	vi m(n), l(n);
	for(int i = 0; i < n; i++){
		cin >> m[i] >> l[i];
	}
	if(solve(0, m, l)){
		cout << "Yes\n";
		return 0;
	}
	cout << "No\n";
	return 0;
}

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