Submission #274976

#	Time	Username	Problem	Language	Result	Execution time	Memory
274976		ainta	Shopping Plans (CCO20_day2problem3)	C++17	25 / 25	339 ms	62260 KiB

Main

#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#define N_ 201000
using namespace std;
int n, m, K;
struct QQ{
    long long s;
    int a;
    int isB;
    int c;
    int pv; // in a, c chosen, pv-th, ~ed
    int cur;
    int ed;
    bool operator <(const QQ &p)const{
        return s>p.s;
    }
};
priority_queue<QQ>PQ;
void Put(long long s, int a, int isB, int c, int pv, int cur, int ed){
    //printf("%lld %d %d %d %d %d %d\n",s,a,isB,c,pv,cur,ed);
    QQ t = {s,a,isB,c,pv,cur,ed};
    PQ.push(t);
}
struct AA{
    vector<int>G;
    int b, e, sz;
    int dif;
    bool operator <(const AA &p)const{
        return dif<p.dif;
    }
}U[N_],w[N_];
int cnt;
vector<long long>Res;
int main(){
    int i, j;
    scanf("%d%d%d",&n,&m,&K);
    for(i=1;i<=n;i++){
        int a, b;
        scanf("%d%d",&a,&b);
        U[a].G.push_back(b);
    }
    long long s=0;
    for(i=1;i<=m;i++){
        U[i].sz = U[i].G.size();
        scanf("%d%d",&U[i].b,&U[i].e);
        if(U[i].sz < U[i].b){
            for(i=0;i<K;i++)puts("-1");
            return 0;
        }
        U[i].e=min(U[i].e,U[i].sz);
        sort(U[i].G.begin(),U[i].G.end());
        for(j=0;j<U[i].b;j++)s+=U[i].G[j];
        if(U[i].b==U[i].sz || U[i].e==0)continue;
        cnt++;
        w[cnt].dif=U[i].G[U[i].b];
        if(U[i].b)w[cnt].dif -= U[i].G[U[i].b-1];
        w[cnt].b=U[i].b,w[cnt].e=U[i].e,w[cnt].sz=U[i].sz, w[cnt].G=U[i].G;
    }
    sort(w+1,w+cnt+1);
//    printf("%d %d\n",w[1].dif,w[2].dif);
//    printf("%d\n",cnt);
    Res.push_back(s);
    if(cnt){
        if(w[1].b)Put(s+w[1].dif, 1, 1, w[1].b, w[1].b, w[1].b+1, w[1].sz);
        else Put(s+w[1].dif, 1, 1, 1, 1, 1, w[1].sz);
    }
    while(!PQ.empty() && Res.size()<K){
        QQ tp = PQ.top();
        s = tp.s;
        Res.push_back(s);
        //printf("%lld\n",tp.s);
        PQ.pop();
        int a = tp.a;
        if(tp.isB && tp.c<w[a].e){
            //puts("11\n");
            if(w[a].b) Put(s + w[a].G[tp.c-1], a, 0, tp.c+1, tp.c+1, tp.c+1, w[a].sz);
        }
        if(tp.isB && a != cnt){
            //puts("22\n");
            if(w[a+1].b)Put(s - w[a].dif + w[a+1].dif, a+1, 1, w[a+1].b, w[a+1].b, w[a+1].b+1, w[a+1].sz);
            else Put(s - w[a].dif + w[a+1].dif, a+1, 1, 1, 1, 1, w[a+1].sz);
        }
        if(a!=cnt){
            //puts("33\n");
            if(w[a+1].b)Put(s + w[a+1].dif, a+1, 1, w[a+1].b, w[a+1].b, w[a+1].b+1, w[a+1].sz);
            else Put(s + w[a+1].dif, a+1, 1, 1, 1, 1, w[a+1].sz);
        }
        if(tp.c==tp.pv && tp.pv==tp.cur && tp.c<w[a].e){
            //puts("44\n");
            Put(s + w[a].G[tp.c], a, 0, tp.c+1, tp.c+1, tp.c+1, w[a].sz);
        }
        if(tp.cur < tp.ed){
            //puts("55\n");
            Put(s - w[a].G[tp.cur-1] + w[a].G[tp.cur], a, 0, tp.c, tp.pv, tp.cur+1, tp.ed);
        }
        if(tp.pv!=1 && tp.cur!=tp.pv){
            //puts("66\n");
            Put(s-w[a].G[tp.pv-2]+w[a].G[tp.pv-1], a, 0, tp.c, tp.pv-1, tp.pv, tp.cur-1);
        }
    }
    for(auto &t : Res)printf("%lld\n",t);
    for(i=Res.size();i<K;i++)puts("-1");
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:69:36: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   69 |     while(!PQ.empty() && Res.size()<K){
      |                          ~~~~~~~~~~^~
Main.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   38 |     scanf("%d%d%d",&n,&m,&K);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
Main.cpp:41:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   41 |         scanf("%d%d",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~
Main.cpp:47:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   47 |         scanf("%d%d",&U[i].b,&U[i].e);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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