oj.uz

Submission #809690

# Submission time Handle Problem Language Result Execution time Memory
809690 2023-08-06T03:00:51 Z Username4132 Akcija (COCI21_akcija) C++14
30 / 110
 4 ms 916 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 596 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 380 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 592 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 1 ms 468 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 596 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 380 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 592 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 2 ms 596 KB Output is correct
16 Correct 2 ms 596 KB Output is correct
17 Correct 2 ms 596 KB Output is correct
18 Correct 1 ms 596 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 516 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 468 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 848 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 916 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 596 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 380 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 592 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 2 ms 596 KB Output is correct
16 Correct 2 ms 596 KB Output is correct
17 Correct 2 ms 596 KB Output is correct
18 Correct 1 ms 596 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 516 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Incorrect 2 ms 848 KB Output isn't correct
28 Halted 0 ms 0 KB -