Submission #154292

#	Time	Username	Problem	Language	Result	Execution time	Memory
154292		alireza_kaviani	Remittance (JOI19_remittance)	C++17	100 / 100	882 ms	44680 KiB

remittance

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

using namespace std;
using namespace __gnu_pbds;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;

#define all(x)                      (x).begin(),(x).end()
#define Sort(x)                     sort(all((x)))
#define X                           first
#define Y                           second
#define Mp                          make_pair
#define sep                         ' '
#define endl                        '\n'
#define debug(x)                    cerr << #x << " = " << x << endl
#define SZ(x)                       ll(x.size())
#define fast_io                     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define set_random                  mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

ll poww(ll a, ll b, ll md) {
    return (!b ? 1 : (b & 1 ? a * poww(a * a % md, b / 2, md) % md : poww(a * a % md, b / 2, md) % md));
}

set_random;

const ll MAXN = 1e6 + 10;
const ll INF = 8e18;
const ll MOD = 1e9 + 7; // 998244353; // 1e9 + 9;

ll n , cnt , A[MAXN] , B[MAXN];
queue<ll> q;

int main() {
    fast_io;

    cin >> n;
    for(ll i = 0 ; i < n ; i++){
        cin >> A[i] >> B[i];
        if(A[i] > B[i]) q.push(i);
    }

    while(!q.empty() && cnt <= 3e7){
        ll i = q.front() , j = (i + 1) % n , t = (A[i] - B[i] + 1) / 2 , inqueue = 0;
        q.pop();
        if(A[i] - t * 2 < 0){
            q.push(i);
            cnt++;
            continue;
        }
        if(A[j] > B[j]) inqueue = 1;

        A[i] -= t * 2;
        A[j] += t;
        if(A[i] > B[i]) q.push(i);
        if(!inqueue && A[j] > B[j]){
            q.push(j);
        }
        cnt++;
    }

    for(ll i = 0 ; i < n ; i++){
        if(A[i] != B[i])    return cout << "No" << endl , 0;
    }
    cout << "Yes" << endl;

    return 0;
}
/*

*/

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