-
Notifications
You must be signed in to change notification settings - Fork 0
/
17612.cpp
50 lines (50 loc) · 1.19 KB
/
17612.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <cstdio>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;
int N,k;
pair<int,int> a[1000000];
struct P{
int id,t,pos;
};
struct cmp{
bool operator()(P& a,P& b){
if(a.t > b.t) return true;
else if(a.t == b.t){
if(a.pos<b.pos) return true;
}
return false;
}
};
int main(){
scanf("%d%d",&N,&k);
for(int i=0;i<N;i++) scanf("%d%d",&a[i].first,&a[i].second);
priority_queue<P,vector<P>,cmp> pq;
int i=0;
for(;i<N&&i<k;i++) pq.push({a[i].first,a[i].second,i});
vector<int> ans;
for(;i<N;i++){
auto [id,t,pos] = pq.top();
vector<int> rp;
while(!pq.empty() && pq.top().t==t){
rp.push_back(pq.top().pos);
ans.push_back(pq.top().id);
pq.pop();
}
reverse(rp.begin(),rp.end());
for(auto r : rp){
pq.push({a[i].first,t+a[i].second,r});
i++;
if(i>=N) break;
}
i--;
}
while(!pq.empty()){
auto [id,t,pos] = pq.top(); pq.pop();
ans.push_back(id);
}
long long total=0;
for(int i=1;i<=N;i++) total+=i*(long long)ans[i-1];
printf("%lld",total);
}