Cod sursa(job #1201569)

Utilizator catalinrebegeaUNIBUC-Claudia Catarig catalinrebegea Data 25 iunie 2014 14:34:02
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.63 kb
#include <cstdio>
#define Nmax 100005

using namespace std;

long long dp[Nmax],q[Nmax],st=1,dr,c[Nmax],p[Nmax];

int main()
{
    int N,T,S,i;
    long long sol=0;
    freopen ("branza.in","r",stdin);
    freopen ("branza.out","w",stdout);
    scanf("%d%d%d", &N,&S,&T);
    for(i=1;i<=N;++i)
        scanf("%lld%lld", &c[i],&p[i]);
    for(i=1;i<=N;++i)
    {
        while(st<=dr && q[st]<i-T)
            ++st;
        while(st<=dr && c[q[dr]]-q[dr]*S>=c[i]-i*S)
            --dr;
        q[++dr]=i;
        dp[i]=c[q[st]]+(i-q[st])*S;
        sol+=dp[i]*p[i];
    }
    printf("%lld\n", sol);
    return 0;
}