Submission #1051576

#	Time	Username	Problem	Language	Result	Execution time	Memory
1051576		lakshith_	Jobs (BOI24_jobs)	C++14	0 / 100	117 ms	14420 KiB

Main

/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long n,s;cin>>n>>s;
    vector<pair<long long,long long>>arr(n);
    for (int i = 0;i<n;++i){
        cin>>arr[i].first>>arr[i].second;
    }
    vector<int>parent(n);
    vector<long long>cost(n),pos(n,1),remaining(n,0);
    function<int(int,long long,long long)>findsets = [&](int v,long long c,long long r){
      if (parent[v] == v)return v;
      parent[v] = findsets(parent[v],cost[v] + c,r + remaining[v]);
      cost[v]+=c;
      remaining[v]+=r;
      return parent[v];
    };
    vector<int>order(n);
    iota(order.begin(),order.end(),0);
    sort(order.begin(),order.end(),[&](int i,int j){
        if (arr[i].second == arr[j].second)return arr[i].first > arr[j].first;
      return arr[i].second < arr[j].second;  
    });
    long long ans = 0;
    for (int i = 0;i<n;){
        int j = i;
        while(j < n && arr[order[i]].second == arr[order[j]].second){
            ++j;
        }
        //cout<<i<<" "<<j<<'\n';
        for (int kk = i;kk<j;++kk){
            int k = order[kk];
            if (arr[k].second == 0){
                cost[k] = arr[k].first;
                parent[k] = k;
                //if (-cost[k] + ans > s)pos[k] = 0;
                remaining[k] = arr[k].first;
                if (remaining[k] > 0){
                    ans+=remaining[k];
                    remaining[k] = 0;
                }
            }
            else{
                cost[k] = arr[k].first;
                remaining[k] = arr[k].first;
                int vv = findsets(arr[k].second - 1,0,0);
                if (-cost[vv] - ans > s){
                    pos[vv] = 0;
                }
                parent[k] = vv;
                //cout<<k<<" "<<vv<<" "<<remaining[vv]<<" "<<arr[k].first<<" "<<pos[vv]<<" "<<cost[vv]<<'\n';
                if (pos[vv] && remaining[vv] + arr[k].first > 0){
                    ans+=remaining[vv] + arr[k].first;
                    remaining[k] = 0;
                    remaining[vv] = 0;
                }
            }
        }
        //cout<<ans<<'\n';
        i = j;
    }
    cout<<ans<<'\n';
    return 0;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 29
• Subtask 5: 0 / 31