Cod sursa(job #963358)

Utilizator mihail.jianuJianu Mihail mihail.jianu Data 17 iunie 2013 11:47:02
Problema Branza Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.68 kb
#include<cstdio>
#define ll long long
const int N=100001;
struct sapt{
    ll c,p;
};
sapt v[N];
ll d[N];
ll s[N];
ll n,t,i,sapt;
ll nr;
int main(){
    freopen("branza.in","r",stdin);
    freopen("branza.out","w",stdout);
    scanf("%lld%lld%lld",&n,&t,&sapt);
    for(i=1;i<=n;i++)
        scanf("%lld%lld",&v[i].c,&v[i].p);
    //sapt--;
    sapt++;
    d[1]=1;
    s[1]=v[1].c*v[1].p;
    for(i=2;i<=n;i++){
        s[i]=v[i].c*v[i].p+s[i-1];
        d[i]=i;
        nr=t*v[i].p*(i-d[i-1])+s[i-1]+v[d[i-1]].c*v[i].p;
        if(nr<s[i] && i-d[i-1]<=sapt){
            s[i]=nr;
            d[i]=d[i-1];
        }
    }
    printf("%lld",s[n]);
    return 0;
}