Cod sursa(job #2545087)

Utilizator AndreiD31Dragan Andrei AndreiD31 Data 12 februarie 2020 20:22:57
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("branza.in");
ofstream g("branza.out");

int arb[4*100100],lazy[4*100100];

void update_arb(int nod,int st,int dr,int a,int b,int val)
{
    if(a<=st && dr<=b)
    {
        arb[nod]+=val;
        lazy[nod]+=val;
    }
    else
    {
        int m=(st+dr)/2;
        if(m>=a)update_arb(2*nod,st,m,a,b,val+lazy[nod]);
        if(m+1<=b)update_arb(2*nod+1,m+1,dr,a,b,val+lazy[nod]);

        arb[nod]=min(arb[2*nod],arb[2*nod+1]);
    }
}

int querry_arb(int nod,int st,int dr,int a,int b)
{
    if(a<=st && dr<=b)return arb[nod];
    else
    {
        int m=(st+dr)/2,x1=INT_MAX,x2=INT_MAX;
        if(m>=a)x1=querry_arb(2*nod,st,m,a,b);
        if(m+1<=b)x2=querry_arb(2*nod+1,m+1,dr,a,b);

        return min(x1,x2);
    }
}

int n,S,suma,cost,cant,cap1,t,i;
int main()
{
    f>>n>>S>>t;

    for(i=1;i<=n;i++)
    {
        f>>cost>>cant;

        cap1=max(1,i-t+1);
        update_arb(1,1,n,i,i,cost);
        if(i-1>=1)update_arb(1,1,n,cap1,i-1,S);

        int min_val=querry_arb(1,1,n,cap1,i);
        suma+=min_val*cant;
    }

    g<<suma;
    return 0;
}