#include<bits/stdc++.h>
using namespace std;
#define int long long
struct S{
int d,c,i;
};
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
#ifndef ONLINE_JUDGE
freopen("be1.txt","r",stdin);
#endif
int N,K;
cin>>N>>K;
deque<S>q;
map<int,int>m;
int t=0;
int ans=0;
for(int i=1;i<=N;i++){
int d,c;
cin>>d>>c;
while(!q.empty()&&c<q.back().c){
t-=q.back().d;
q.pop_back();
}
if(t<K){
q.push_back({K-t,c,i});
}
t=K;
while(!q.empty()&&q.front().d<=d){
m[q.front().i]+=q.front().d;
ans+=q.front().c*q.front().d;
d-=q.front().d;
t-=q.front().d;
q.pop_front();
}
if(!q.empty()&&d>0){
m[q.front().i]+=d;
ans+=q.front().c*d;
q.front().d-=d;
t-=d;
}
}
cout<<ans<<' '<<m.size()<<'\n';
for(auto[a,b]:m){
cout<<a<<' '<<b<<'\n';
}
return 0;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 100/100 | ||||||
1 | Elfogadva | 0/0 | 3ms | 1828 KiB | |||
2 | Elfogadva | 0/0 | 61ms | 2228 KiB | |||
3 | Elfogadva | 5/5 | 3ms | 2228 KiB | |||
4 | Elfogadva | 5/5 | 3ms | 2444 KiB | |||
5 | Elfogadva | 5/5 | 3ms | 2652 KiB | |||
6 | Elfogadva | 5/5 | 3ms | 2868 KiB | |||
7 | Elfogadva | 5/5 | 3ms | 3080 KiB | |||
8 | Elfogadva | 5/5 | 3ms | 3160 KiB | |||
9 | Elfogadva | 5/5 | 3ms | 3160 KiB | |||
10 | Elfogadva | 5/5 | 3ms | 3164 KiB | |||
11 | Elfogadva | 5/5 | 21ms | 3988 KiB | |||
12 | Elfogadva | 5/5 | 32ms | 4520 KiB | |||
13 | Elfogadva | 5/5 | 19ms | 3532 KiB | |||
14 | Elfogadva | 5/5 | 37ms | 3620 KiB | |||
15 | Elfogadva | 5/5 | 96ms | 12024 KiB | |||
16 | Elfogadva | 5/5 | 92ms | 11576 KiB | |||
17 | Elfogadva | 5/5 | 94ms | 11620 KiB | |||
18 | Elfogadva | 5/5 | 89ms | 11244 KiB | |||
19 | Elfogadva | 5/5 | 150ms | 15416 KiB | |||
20 | Elfogadva | 5/5 | 153ms | 16028 KiB | |||
21 | Elfogadva | 5/5 | 162ms | 16464 KiB | |||
22 | Elfogadva | 5/5 | 165ms | 16860 KiB |