Cod sursa(job #107131)

Utilizator ZeusCatalin Tiseanu Zeus Data 19 noiembrie 2007 12:15:14
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb

#include <cstdio>
#include <iostream>

using namespace std;

#define LL long long

int N, S, T, C[1<<17], P[1<<17];
LL tmp[1<<17], tot_cas[1<<17];

inline LL cost( int x )
{
    return ( (LL)N - x ) * (LL)S + C[x];          
}

int main()
{
    freopen("branza.in", "r", stdin);
    freopen("branza.out", "w", stdout);
    
    int deq[1<<17], fi, la;
    
    scanf("%d %d %d", &N, &S, &T);
    for( int i = 1; i <= N; ++i ) 
         scanf("%d %d", C + i, P + i );
    
    deq[ fi = la = 0 ] = 1;
    
    tmp[1] = C[1];
    
    for( int i = 1; i <= N; ++i )
    {
         while( fi <= la && i - deq[fi] > T )
                ++fi;
         
         int el = deq[fi];
         LL real = cost(el) - ( (LL)N - i ) * (LL)S;
         
//         printf("%d\n", el );
         
         tmp[i] = real;
         
         while( fi <= la && cost( i + 1 ) <= cost( deq[la] ) )
               --la;
               
         deq[++la] = i + 1;      
    }
    
    LL ret = 0;
    
    for( int i = 1; i <= N; ++i )
         ret += tmp[i] * P[i];
         
    cout << ret << endl;
    
    return 0;
}