This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18;
struct type
{
int x,y;
int sz;
vector<int>lst;
int fdif;
type(){}
};
struct node
{
ll val;
int ci,cn;
int ith,pos,mx;
bool fi;
node(ll val,int ci,int cn,int ith,int pos,int mx,bool fi=0):
val(val),ci(ci),cn(cn),ith(ith),pos(pos),mx(mx),fi(fi){}
bool operator<(const node&x)const
{
return val==x.val?fi&&!x.fi:val>x.val;
}
};
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n,m,k;
cin>>n>>m>>k;
vector<vector<int> >vv(m);
for(int i=0;i<n;i++)
{
int a,c;
cin>>a>>c;
vv[a-1].eb(c);
}
vector<type>tpv;
ll fi=0;
for(auto&v:vv)
{
int x,y;
cin>>x>>y;
sort(all(v));
y=min(y,(int)v.size());
if(x>y)
{
for(int i=0;i<k;i++)
cout<<"-1\n";
return 0;
}
for(int i=0;i<x;i++)
fi+=v[i];
if((int)v.size()>x)
{
tpv.eb(type());
if(x==0)
tpv.back().fdif=v[0];
else
tpv.back().fdif=v[x]-v[x-1];
tpv.back().x=x,tpv.back().y=y;
tpv.back().lst=v;
tpv.back().sz=v.size();
}
}
sort(all(tpv),[](const type&x,const type&y){return x.fdif<y.fdif;});
vector<ll>ansv;
ansv.eb(fi);
priority_queue<node>pq;
if(!tpv.empty())
{
if(tpv[0].x==0)
pq.ep(fi+tpv[0].fdif,0,tpv[0].x,0,-1,-1,1);
else
pq.ep(fi+tpv[0].fdif,0,tpv[0].x,tpv[0].x-1,tpv[0].x-1,tpv[0].sz-1,1);
}
int tps=tpv.size();
while(!pq.empty()&&(int)ansv.size()<k)
{
node cur=pq.top();
pq.pop();
const type&tp=tpv[cur.ci];
if(cur.first)
cur.val-=tp.fdif;
else
ansv.eb(cur.val);
if(cur.ith>0&&cur.pos>cur.ith)
pq.ep(cur.val-tp.lst[cur.ith-1]+tp.lst[cur.ith],cur.ci,cur.cn,cur.ith-1,cur.ith,cur.pos-1);
if(cur.pos<cur.mx)
pq.ep(cur.val-tp.lst[cur.pos]+tp.lst[cur.pos+1],cur.ci,cur.cn,cur.ith,cur.pos+1,cur.mx);
if(cur.pos==cur.cn-1&&cur.cn<tp.y)
pq.ep(cur.val+tp.lst[cur.cn],cur.ci,cur.cn+1,cur.cn,cur.cn,cur.mx);
if(cur.ci+1<tps)
{
const type&ntp=tpv[cur.ci+1];
if(ntp.x==0)
pq.ep(cur.val+ntp.fdif,cur.ci+1,ntp.x,0,-1,-1,1);
else
pq.ep(cur.val+ntp.fdif,cur.ci+1,ntp.x,ntp.x-1,ntp.x-1,ntp.sz-1,1);
}
}
while((int)ansv.size()<k)
ansv.eb(-1);
for(ll&t:ansv)
cout<<t<<'\n';
return 0;
}
Compilation message (stderr)
Main.cpp: In function 'int main()':
Main.cpp:16:8: warning: '<anonymous>.type::x' may be used uninitialized in this function [-Wmaybe-uninitialized]
16 | struct type
| ^~~~
Main.cpp:16:8: warning: '<anonymous>.type::y' may be used uninitialized in this function [-Wmaybe-uninitialized]
Main.cpp:16:8: warning: '<anonymous>.type::sz' may be used uninitialized in this function [-Wmaybe-uninitialized]
Main.cpp:16:8: warning: '<anonymous>.type::fdif' may be used uninitialized in this function [-Wmaybe-uninitialized]
# | 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... |