제출 #797330

#제출 시각아이디문제언어결과실행 시간메모리
797330fatemetmhrRemittance (JOI19_remittance)C++17
0 / 100
1 ms340 KiB
    // Be name khoda // 
     
    #include <bits/stdc++.h>
     
    #define all(x) x.begin(), x.end()
    #define pb     push_back
    #define fi     first
    #define se     second
    #define mp     make_pair
     
    typedef long long ll;
     
    using namespace std;
     
    const int maxn5 = 1e6 + 10;
    const ll inf    = 1e18;
     
    bool mark[maxn5];
    ll a[maxn5], b[maxn5];
    queue <int> q;
     
    int n;
    bool found = false;
     
     
    void solve(int lev, int cnt){
    	bool re = true;
    	for(int i = 0; i < n; i++)
    		re &= (a[i] == b[i]);
    	if(re){
    		found = true;
    		return;
    	}
    	if(cnt == n)
    		return;	
    	for(int x = 2; x <= a[lev]; x+= 2){
    		a[lev] -= x;
    		a[(lev + 1)%n] += x / 2;
    		solve((lev + 1) % n, 0);
    		if(found)
    			return;
    		a[lev] += x;
    		a[(lev + 1)%n] -= x / 2;
    	}
    	solve((lev + 1)%n, cnt + 1);
     
    }
     
    int main(){
    	ios_base::sync_with_stdio(false); cin.tie(0);
     
    	cin >> n;
    	ll sum = 0;
    	for(int i = 0; i < n; i++){
    		cin >> a[i] >> b[i];
    		sum += a[i];
    	}
    	//solve(0, 0);
    	//cout << (found ? "Yes" : "No") << endl;
    	//return 0;
    	while(sum >= 0){
    		bool re = true;
    		for(int i = 0; i < n; i++){
    			if(a[i] > b[i]){
    				int j = (i + 1) % n;
    				ll w = (a[i] - b[i]) / 2 + ((a[i] - b[i]) % 2);
    				a[j] += w;
    				a[i] -= 2 * w;
    				sum -= w;
    				re = false;
    			}
    		}
    		if(re){
    			for(int i = 0; i < n; i++)
    				re &= (a[i] == b[i]);
    			if(!re)
    				break;
    			return cout << "Yes" << endl, 0;
    		}
    	}
    	cout << "No" << endl;
     
    }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...