이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/******************************************************************************
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;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |