Pagini recente » Cod sursa (job #2906541) | Cod sursa (job #980618) | Cod sursa (job #2834733) | Statistici Bujo Catalin (xxennon) | Cod sursa (job #443277)
Cod sursa(job #443277)
#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<<a<<"\n";
}
g<<rez<<"\n";
f.close();
g.close();
return 0;
}