Submission #1241507

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241507		trantrungkein	Remittance (JOI19_remittance)	C++20	55 / 100	1097 ms	44464 KiB

remittance

#include <bits/stdc++.h>
 #define int long long 
#define fi           first 
#define si           second 
#define For(i,a,b)   for (int i = (a), _b =(b); i <= _b; ++i)
#define all(v)       v.begin(), v.end()
#define Unique(v)    v.erase(unique(all(v)), v.end())   
#define MASK(i)      (1LL << (i))
#define bit(i,n)     (((n)>>(i)) & 1)
#define Vii          vector<pair<int,int>>
#define setpr(x)     cout<<setprecision(x)<<fixed
#define Prior        priority_queue< pair<int,int> , Vii, greater<Pair> >
using namespace std;
 
const int Mod = 1E9 + 7;
const long long INF  = 4E18;
const int N = 1e6 + 1;
struct node
{
    int id,value,val;
    bool operator < (const node & other) const
    {
        return val < other.val;
    }
};
priority_queue<node> q;
int n,a[N],b[N],curr[N];
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    //freopen("kein.inp","r",stdin)
    //freopen("kein.out","w",stdout);
    cin >> n;
    For(i,1,n)
    {
        cin >> a[i] >> b[i];
        curr[i] = a[i];
        if(a[i] > b[i])
        {   
            if((a[i]-b[i])%2==0) q.push({i,a[i],a[i]-b[i]});
            else if(b[i] != 0)
            {   //cout << i << endl
                q.push({i,a[i],a[i]-b[i]+1});
            }
        }
        //cout << "GG" << i <<' ' << curr[i] <<'\n';
    }
    //cout <<"GG" << curr[2] << endl;
    while(!q.empty())
    {
        auto [id,value,diff] = q.top();q.pop();
        if(curr[id] != value) continue;
      //  cout << id <<' ' << value <<' ' << diff << endl;
        int nxt = id + 1;
        if(nxt > n) nxt = 1;
        //cout << curr[nxt] <<' ' << nxt << ' ' << curr[2] << endl;
        curr[nxt] += (diff/2);
        curr[id] -= diff;
       // cout << curr[nxt] <<' ' << nxt << endl;
        if(curr[nxt] > b[nxt])
        {
            if((curr[nxt] - b[nxt])%2==0) q.push({nxt,curr[nxt],curr[nxt] - b[nxt]});
            else if(b[nxt] != 0)
            {
                q.push({nxt,curr[nxt],curr[nxt] - b[nxt] + 1});
            }
        }       
    }
    For(i,1,n)
    {   //cout << curr[i] <<' ';
        if(curr[i] != b[i]) 
        {
            cout << "No"; return 0;
        }
    }
    cout << "Yes";
}

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