#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int c=3e5+5;
int n,k,fuel;
ll pref[c],prc[c];
int best[c];
ll tot;
vector<pair<int,int>> ans;
stack<int> s;
ll dist(int i, int j){
return pref[j]-pref[i];
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>pref[i+1]>>prc[i];
pref[i+1]+=pref[i];
}
prc[n+1]=-1;
s.push(n+1);
for(int i=n;i>=1;i--){
while(prc[i]<prc[s.top()]){
s.pop();
}
best[i]=s.top();
s.push(i);
}
int cur=1; fuel=0;
while(cur <= n){
int d=dist(cur,best[cur]);
if(d > k){
//if(cur==3) cout << d << endl;
int nw=k-fuel;
if(nw>0){
fuel+=nw;
tot+=prc[cur]*nw;
ans.push_back(make_pair(cur,nw));
}
fuel-=dist(cur,cur+1);
++cur;
}
else{
int nw=d-fuel;
if(nw>0){
fuel+=nw;
tot+=prc[cur]*nw;
ans.push_back(make_pair(cur,nw));
}
fuel-=dist(cur,best[cur]);
cur=best[cur];
}
}
cout << tot << ' ' << ans.size() << '\n';
for(pair<int,int> x:ans){
cout << x.first << ' ' << x.second << '\n';
}
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 100/100 | ||||||
1 | Elfogadva | 0/0 | 2ms | 1832 KiB | |||
2 | Elfogadva | 0/0 | 52ms | 15392 KiB | |||
3 | Elfogadva | 5/5 | 1ms | 3632 KiB | |||
4 | Elfogadva | 5/5 | 1ms | 3636 KiB | |||
5 | Elfogadva | 5/5 | 1ms | 3644 KiB | |||
6 | Elfogadva | 5/5 | 1ms | 3648 KiB | |||
7 | Elfogadva | 5/5 | 1ms | 3648 KiB | |||
8 | Elfogadva | 5/5 | 1ms | 3656 KiB | |||
9 | Elfogadva | 5/5 | 1ms | 3656 KiB | |||
10 | Elfogadva | 5/5 | 1ms | 3704 KiB | |||
11 | Elfogadva | 5/5 | 13ms | 6628 KiB | |||
12 | Elfogadva | 5/5 | 18ms | 8580 KiB | |||
13 | Elfogadva | 5/5 | 17ms | 8704 KiB | |||
14 | Elfogadva | 5/5 | 32ms | 13360 KiB | |||
15 | Elfogadva | 5/5 | 45ms | 16724 KiB | |||
16 | Elfogadva | 5/5 | 43ms | 16652 KiB | |||
17 | Elfogadva | 5/5 | 41ms | 17968 KiB | |||
18 | Elfogadva | 5/5 | 39ms | 18688 KiB | |||
19 | Elfogadva | 5/5 | 64ms | 25360 KiB | |||
20 | Elfogadva | 5/5 | 64ms | 26196 KiB | |||
21 | Elfogadva | 5/5 | 68ms | 28548 KiB | |||
22 | Elfogadva | 5/5 | 67ms | 29416 KiB |