Pagini recente » Cod sursa (job #1579661) | Cod sursa (job #2100509) | Cod sursa (job #2447936) | Cod sursa (job #149155) | Cod sursa (job #2340041)
#include <fstream>
#include <deque>
#define DIM 100001
using namespace std;
int cnt[DIM],best[DIM],p[DIM];
deque <int> Min;
int main()
{ int 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);
int j=Min.front();
best[i]=p[j]+s*(i-j);
if (i-t+1==Min.front()) Min.pop_front();
}
for (i=1;i<=n;++i)
sol+=cnt[i]*best[i];
g<<sol;
return 0;
}