제출 #489470

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
489470		Haruto810198	송금 (JOI19_remittance)	C++17	15 / 100	340 ms	262148 KiB

remittance

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define double long double

#define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d))
#define szof(x) ((int)(x).size())

#define vi vector<int>
#define pii pair<int, int>

#define F first
#define S second

#define pb push_back
#define eb emplace_back
#define mkp make_pair

const int INF = INT_MAX;
const int LNF = INF*INF;
const int MOD = 1000000007;

const int MAX = 1000010;

int n;
int init[MAX], target[MAX];
bool res;

set<vi> vis;

void dfs(vi arr){
	
	vis.insert(arr);
	
	bool ok = 1;
	FOR(i, 0, n - 1, 1){
		if(arr[i] != target[i]) ok = 0;
	}

	if(ok){
		res = 1;
		return;
	}
	
	FOR(i, 0, n - 1, 1){
		int ii = (i + 1) % n;
		if(arr[i] >= 2){
			arr[i] -= 2;
			arr[ii] += 1;
			if(vis.find(arr) == vis.end()) dfs(arr);
			arr[i] += 2;
			arr[ii] -= 1;
		}
	}
	
}

signed main(){
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n;
	FOR(i, 0, n - 1, 1){
		cin>>init[i]>>target[i];
	}
	
	vi arr;
	FOR(i, 0, n - 1, 1){
		arr.pb(init[i]);
	}

	dfs(arr);

	if(res) cout<<"Yes"<<'\n';
	else cout<<"No"<<'\n';
	
	return 0;

}

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