Cod sursa(job #2732911)

Utilizator betybety bety bety Data 29 martie 2021 16:14:16
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.72 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("branza.in");
ofstream out("branza.out");
typedef unsigned long long ll;
const ll lim=1e5+4;
const ll inf=2e18+4;
ll cost[lim];
ll cant[lim];
ll sp[lim];
ll dp[lim];
ll n,s,t;
ll depl(ll i,ll j)
{
    return (sp[j]-sp[i-1])*cost[i]+s*(dp[j]-dp[i]-(sp[j]-sp[i])*i);
}
ll ans[lim];
int main()
{
    in>>n>>s>>t;
    for(ll i=1;i<=n;++i)
    {
        in>>cost[i]>>cant[i];
        sp[i]=sp[i-1]+cant[i];
        dp[i]=dp[i-1]+i*cant[i];
    }
    for(ll i=1;i<=n;++i)
    {
        ans[i]=ans[i-1]+depl(i,i);
        for(ll j=i;j>=max((ll)1,i-t);--j)
            ans[i]=min(ans[i],ans[j-1]+depl(j,i));
    }
    out<<ans[n]<<'\n';
    return 0;
}