Submission #286522

#	Time	Username	Problem	Language	Result	Execution time	Memory
286522		gs18115	Shopping Plans (CCO20_day2problem3)	C++14	25 / 25	377 ms	56960 KiB

Main

#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,0,-1,-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.ith==cur.cn-1&&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,tp.sz-1);
        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,0,-1,-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]

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5