Pagini recente » Cod sursa (job #3173904) | Cod sursa (job #1068905) | Cod sursa (job #140737) | Cod sursa (job #2755007) | Cod sursa (job #443279)
Cod sursa(job #443279)
#include<fstream>
#include<list>
using namespace std;
ifstream f("branza.in");
ofstream g("branza.out");
int i,j,n,t,s,p[100005],c[100005],dr,st;
long long a,rez;
struct nod
{
long long x;
int poz;
}deq[100005];
int main()
{
f>>n>>s>>t;
for(i=1;i<=n;++i)
f>>c[i]>>p[i];
st=1;
dr=0;
for(i=1;i<=n;++i)
{
a=0;
if(dr<st)
{
a=c[i];
deq[++dr].x=a+(long long)((n-i)*s);
deq[dr].poz=i;
}
else
{
long long aux=c[i]+(long long)((n-i)*s);
while(dr>=st&&deq[dr].x>aux) --dr;
deq[++dr].x=aux;
deq[dr].poz=i;
a=deq[st].x-(n-i)*s;
if(deq[st].poz==i-t) st++;
}
rez+=(a*(long long)(p[i]));
}
g<<rez<<"\n";
f.close();
g.close();
return 0;
}