Pagini recente » Cod sursa (job #553058) | Cod sursa (job #784264) | Cod sursa (job #2615704) | Cod sursa (job #678721) | Cod sursa (job #2123535)
#include<fstream>
#include<iostream>
#define DN 100005
using namespace std;
ifstream fin("branza.in");
ofstream fout("branza.out");
int n,s,t,c,p,a[4*DN],b[4*DN],poz,r,f,l;
long long rez;
void update(int nod,int st,int dr)
{
if(st==dr)
{
a[nod]=c;
return;
}
int mij=(st+dr)/2;
if(poz<=mij)
{
update(2*nod,st,mij);
a[nod]=min(a[2*nod],a[2*nod+1]);
}
else
{
b[2*nod]+=s;
update(2*nod+1,mij+1,dr);
a[nod]=min(a[2*nod]+b[2*nod],a[2*nod+1]);
}
}
void query(int nod,int st,int dr,int sum)
{
if(f<=st&&dr<=l)
{
r=min(r,a[nod]+sum);
return;
}
int mij=(st+dr)/2;
if(f<=mij)
query(2*nod,st,mij,sum+b[2*nod]);
if(mij<l)
query(2*nod+1,mij+1,dr,sum+b[2*nod+1]);
}
int main()
{
fin>>n>>s>>t;
for(int i=1;i<=n;i++)
{
fin>>c>>p;
poz=i;
update(1,1,n);
r=(1<<30);
f=max(1,i-t);
l=i;
query(1,1,n,0);
cout<<r<<'\n';
rez+=r*p;
}
fout<<rez;
}