# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
891551 | 1075508020060209tc | Shopping Plans (CCO20_day2problem3) | C++14 | 1480 ms | 1048576 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;int m;int K;
vector<int>e[500005];
signed main(){
cin>>n>>m>>K;
for(int i=1;i<=n;i++){
int a;int c;
cin>>a>>c;
e[a].push_back(c);
}
for(int i=1;i<=m;i++){
int a;
cin>>a;
cin>>a;
}
for(int i=1;i<=m;i++){
sort(e[i].begin(),e[i].end());
}
priority_queue<pair<int,pair<int,int>>>pq;
{
int S=0;
for(int i=1;i<=m;i++){
if(e[i].size()==0){
for(int j=1;j<=K;j++){
cout<<"-1\n";
}return 0;
}
S+=e[i][0];
}
pq.push({-S,{0,-1}});
}
while(K--){
if(pq.size()==0){
for(int i=1;i<=K+1;i++){
cout<<"-1\n";
}
return 0;
}
int nwv=pq.top().first;
cout<<-nwv<<"\n";
int nw=pq.top().second.first;
int nww=pq.top().second.second;
// cout<<nw<<" "<<nww<<"\n";
pq.pop();
nwv=-nwv;
if(nw>=1){
if(e[nw].size()>nww+1){
pq.push({-(nwv+-e[nw][nww]+e[nw][nww+1]),{nw,nww+1}});
}
}
for(int j=nw+1;j<=m;j++){
if(e[j].size()>=2){
pq.push({-(nwv+e[j][1]-e[j][0]),{j,1}});
}
}
}
}
Compilation message (stderr)
# | 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... |