Cod sursa(job #2123543)

Utilizator patcasrarespatcas rares danut patcasrares Data 6 februarie 2018 12:51:12
Problema Branza Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include<cstdio>
#include<iostream>
#define DN 100005
using namespace std;
long long 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()
{
    freopen("branza.in","r",stdin);
    freopen("branza.out","w",stdout);
    scanf("%d%d%d",&n,&s,&t);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&c,&p);
        poz=i;
        update(1,1,n);
        r=(1<<30);
        f=max(1LL,i-t);
        l=i;
        query(1,1,n,0);
        rez+=r*p;
    }
    printf("%lld",rez);
}