Submission #1206779

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206779		catch_me_if_you_can	Remittance (JOI19_remittance)	C++20	55 / 100	1096 ms	78680 KiB

remittance

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define in array<int, 2>
#define pb push_back
#define pob pop_back
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)

const int MX = 2e5+5;
const int INF = 1e17;

signed main()
{
	fast();
	int n; cin >> n;
	vector<int> a(n+1);
	vector<int> b(n+1);
	for(int i = 1; i <= n; i++)
		cin >> a[i] >> b[i];
	set<in> cope;
	int S1 = 0;
	int S2 = 0;
	for(int i = 1; i <= n; i++)
	{
		S1+=a[i]; S2+=b[i];
		cope.insert({a[i]-b[i], i});
	}
	while(S1 > S2)
	{
		auto [D, i] = *prev(cope.end());
		cope.erase({a[i]-b[i], i});
		cope.erase({a[i%n + 1]-b[i%n + 1], i%n +1});
		int s = D/2; int K = min(s, D - a[i%n + 1] + b[i%n + 1]); K = max(K, 1ll);
		a[i]-=(2*K); a[i%n +1]+=K; S1-=K;
		if(a[i] < 0)
		{
			S1 = INF;
			break;
		}
		cope.insert({a[i]-b[i], i}); 
		cope.insert({a[i%n + 1]-b[i%n + 1], i%n + 1});
	}
	if(S1 > S2)
	{
		cout << "No\n";
		return 0;
	}
	bool works = true;
	for(int i = 1; i <= n; i++)
	{
		if(a[i] != b[i])
			works = false;
	}
	if(works)
		cout << "Yes\n";
	else
		cout << "No\n";
	return 0;
}	

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