Pagini recente » Cod sursa (job #2551008) | Cod sursa (job #2011711) | Cod sursa (job #29231) | Cod sursa (job #1963176) | Cod sursa (job #382188)
Cod sursa(job #382188)
#include<iostream>
#include<fstream>
using namespace std;
ifstream f("branza.in");
ofstream g("branza.out");
long long c[1<<17],p[1<<17],dr=0,st=1,dq[1<<17],t,s,n;
inline void stanga(int i)
{
if (i>t && dq[st]==i-t)
++st;
}
void dreapta(int i)
{
while(st<=dr&&c[dq[dr]]+(i-dq[dr])*s>=c[i])
--dr;
dq[++dr]=i;
}
int main()
{
f>>n>>s>>t;
++t;
long long i,nrf=0;
for(i=1;i<=n; ++i)
f>>c[i]>>p[i];
for(i=1; i<=n; ++i)
{
stanga(i);
dreapta(i);
nrf=nrf+(c[dq[st]]+(i-dq[st])*s)*p[i];
}
g<<nrf;
f.close();g.close();
return 0;
}