Pagini recente » Cod sursa (job #2090287) | Cod sursa (job #1097601) | Cod sursa (job #2581365) | Cod sursa (job #1807298) | Cod sursa (job #514393)
Cod sursa(job #514393)
#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[i]<=c[dq[dr]] + (long long)s * (i-dq[dr]))
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]]+(long long)s*(i-dq[st]))*p[i];
}
for(;i<=n;i++)
{
stanga(i);
dreapta(i);
adauga(i);
sum+=(c[dq[st]]+(long long)s*(i-dq[st]))*p[i];
}
out<<sum<<"\n";
return 0;
}