Pagini recente » Cod sursa (job #2897473) | Cod sursa (job #2386230) | Cod sursa (job #2958465) | Cod sursa (job #3236528) | Cod sursa (job #3291542)
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;
ifstream fin("branza.in");
ofstream fout("branza.out");
const int MAX=1e5;
int n,t,s,c[MAX+5],p[MAX+5],i,dp[MAX+5];
int sol;
deque <int> dq;
int main()
{
fin>>n>>s>>t;
for (i=1; i<=n; i++)
fin>>c[i]>>p[i];
for (i=1; i<=n; i++)
{
while (dq.front()<i-t)
dq.pop_front();
while (!dq.empty() && c[dq.back()]-dq.back()*s>c[i]-i*s)
dq.pop_back();
dq.push_back(i);
dp[i]=i*s+c[dq.front()]-dq.front()*s;
}
for (i=1; i<=n; i++)
sol=sol+dp[i]*p[i];
fout<<sol;
return 0;
}