Cod sursa(job #2123538)

Utilizator patcasrarespatcas rares danut patcasrares Data 6 februarie 2018 12:46:06
Problema Branza Scor 60
Compilator cpp Status done
Runda rar9 Marime 1.08 kb
#include<fstream>
#include<iostream>
#define DN 100005
using namespace std;
ifstream fin("branza.in");
ofstream fout("branza.out");
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()
{
    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(1LL,i-t);
        l=i;
        query(1,1,n,0);
        rez+=r*p;
    }
    fout<<rez;
}