Submission #809690

#	Time	Username	Problem	Language	Result	Execution time	Memory
809690		Username4132	Akcija (COCI21_akcija)	C++14	30 / 110	4 ms	916 KiB

Main

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define forsn(i, s, n) for(int i=s; i<(int)n; ++i)
#define dforn(i, n) for(int i=n-1; i>=0; --i)
#define dforsn(i, s, n) for(int i=n-1; i>=s; --i)
#define PB push_back
#define F first
#define S second
#define MP make_pair

struct node{
    int pos, par, er;
    pil cost;
    node(int _pos=0, int _par=0, int _er=0, pil _cost={0, 0}) : pos(_pos), par(_par), er(_er), cost(_cost) {}
};

bool operator<(node a, node b){
    return MP(a.cost.F, -a.cost.S) < MP(b.cost.F, -b.cost.S);
}

const int MAXN = 2010;
int n, k, we[MAXN], tim[MAXN];
bool del[MAXN];
vector<node> tr;
priority_queue<node> Q;
vector<pii> arr[MAXN];
vector<pil> best;

void process(int a){
    ll cst=0;
    vector<int> chosen;
    priority_queue<pii, vector<pii>, greater<pii>> els;
    forn(i, n) del[i]=false;
    int cur = a;
    while(cur!=0){
        del[tr[cur].er]=true;
        cur = tr[cur].par;
    }
    int lst=n;
    dforn(i, n){
        for(pii el:arr[i]) if(!del[el.S]) els.push(el);
        if(!els.empty()){
            pii nw = els.top();
            els.pop();
            cst+=nw.F;
            chosen.PB(nw.S);
        }
        if(els.empty()) lst=i;
    }
    best.PB({(int)chosen.size(), cst});
    int xt=els.empty()? 0 : els.top().F;
    for(int el:chosen) if(el>tr[a].er) {
        int nq = tr[a].cost.F;
        ll ncs = cst - we[el];
        if(tim[el] < lst) ncs+=xt;
        else --nq;
        node nd = node((int)tr.size(), a, el, {nq, ncs});
        Q.push(nd);
        tr.PB(nd);
    }
}

int main(){
    scanf("%d %d", &n, &k);
    forn(i, n){
        int w, d; scanf("%d %d", &w, &d);
        we[i]=w, tim[i]=d-1;
        arr[d-1].PB({w, i});
    }
    node nd = node(0, 0, -1, {1000000000, 0});
    Q.push(nd);
    tr.PB(nd);
    while((int)best.size() < k){
        node v = Q.top();
        Q.pop();
        process(v.pos);
    }
    forn(i, k) printf("%d %lld\n", best[i].F, best[i].S);
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:70:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |     scanf("%d %d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:72:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |         int w, d; scanf("%d %d", &w, &d);
      |                   ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 10
• Subtask 5: 0 / 30
• Subtask 6: 0 / 20