Pagini recente » Cod sursa (job #2506171) | Cod sursa (job #370188) | Cod sursa (job #1652996) | Cod sursa (job #2915986) | Cod sursa (job #514390)
Cod sursa(job #514390)
#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]]+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;
}