Pagini recente » Cod sursa (job #1197386) | Cod sursa (job #288819) | Cod sursa (job #359829) | Cod sursa (job #526285) | Cod sursa (job #2340052)
#include <fstream>
#include <deque>
#define DIM 100005
#define ll long long
using namespace std;
ll cnt[DIM],best[DIM],p[DIM];
deque <ll> Min;
int main()
{ ll n,t,s,i,sol=0;
ifstream f("branza.in");
ofstream g("branza.out");
f>>n>>s>>t;
for (i=1;i<=n;++i)
f>>p[i]>>cnt[i];
for (i=1;i<=n;++i) {
while (!Min.empty() && p[i]+s*(n-i)<p[Min.back()]+s*(n-Min.back()))
Min.pop_back();
Min.push_back(i);
ll j=Min.front();
best[i]=p[j]+s*(i-j);
if (i-t==Min.front()) Min.pop_front();
}
for (i=1;i<=n;++i)
sol+=cnt[i]*best[i];
g<<sol;
return 0;
}