이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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);
}
컴파일 시 표준 에러 (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);
| ~~~~~^~~~~~~~~~~~~~~~~
# | 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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |