Pagini recente » Cod sursa (job #1583523) | Cod sursa (job #2590479) | Cod sursa (job #1351999) | Cod sursa (job #2681402) | Cod sursa (job #514392)
Cod sursa(job #514392)
#include <fstream>
using namespace std;
ifstream in ("branza.in");
ofstream out ("branza.out");
const int N=100005;
int c[N],dq[N],p[N];
int n,s,t,st,dr;
long long sum;
void dreapta(int i)
{
while(st<=dr && c[dq[dr]]+(long long)s*(i-dq[dr])>=c[i])
dr--;
}
void stanga(int i)
{
if(i-dq[st]==t)
++st;
}
void adauga(int i)
{
dq[++dr]=i;
}
int main()
{
int i;
in>>n>>s>>t;
st=1;
dr=0;
for(i=1;i<=n;i++)
in>>c[i]>>p[i];
for(i=1;i<=t;i++)
{
dreapta(i);
dq[++dr]=i;
sum+=(c[dq[st]]+(i-dq[st])*s)*p[dq[st]];
}
for(;i<=n;i++)
{
stanga(i);
dreapta(i);
adauga(i);
sum+=(c[dq[st]]+(i-dq[st])*s)*p[i];
}
out<<sum<<"\n";
return 0;
}