Cod sursa(job #67521)

Utilizator devilkindSavin Tiberiu devilkind Data 25 iunie 2007 11:05:47
Problema Branza Scor 0
Compilator cpp Status done
Runda preONI 2007, Runda Finala, Clasa a 10-a Marime 1.98 kb
#include <stdio.h>
#define NMAX 100002

struct node{long int min,sum;} arb[NMAX*3];

long int P[NMAX],C[NMAX],n,t,s;
long int i,j,k;


void citire()
{
freopen("branza.in","r",stdin);
freopen("branza.out","w",stdout);
scanf("%ld %ld %ld",&n,&s,&t);
for (i=1;i<=n;i++)
        scanf("%ld %ld",&P[i],&C[i]);
}

long int MINN(long int a, long int b)
{
if (a<b) return a;
return b;
}

void build(long int nod, long int st, long int dr)
{
if (st==dr) {arb[nod].min=P[st];
             arb[nod].sum=0;
             }
             else
             {
             long int mid=(st+dr)/2;
             build(nod*2,st,mid);
             build(nod*2+1,mid+1,dr);
             arb[nod].sum=0;
             arb[nod].min=MINN(arb[nod*2].min,arb[nod*2+1].min);
             }
}

void update(long int nod,long int st, long int dr, long int a, long int b, long int val)
{
if (a<=st&&dr<=b) {arb[nod].sum+=val;arb[nod].min+=val;}
        else {
             long int mid;
             mid=(st+dr)/2;
             if (a<=mid) update(nod*2,st,mid,a,b,val);
             if (b>mid) update(nod*2+1,mid+1,dr,a,b,val);
             arb[nod].min=MINN(arb[nod*2].min, arb[nod*2+1].min)+arb[nod].sum;
             }
}

long int minim;

void query(long int nod, long int st, long int dr, long int a, long int b, long int sum)
{
if (a<=st&&dr<=b) minim=MINN(arb[nod].min+sum,minim);
        else {
             long int mid;
             mid=(st+dr)/2;
             if (a<=mid) query(nod*2,st,mid,a,b,sum+arb[nod].sum);
             if (b>mid) query(nod*2+1,mid+1,dr,a,b,sum+arb[nod].sum);
             }
}

void solve()
{
long int back,min;
long long cost;

build(1,1,n);

cost=P[1]*C[1];

for (i=2;i<=n;i++)
        {
        back=i-t;
        if (back<1) back=1;
        update(1,1,n,back,i-1,s);
        minim=P[i];
        query(1,1,n,back,i-1,0);
        cost=cost+minim*C[i];
        }
printf("%lld",cost);
}

int main()
{
citire();
solve();
return 0;
}