Cod sursa(job #2582520)

Utilizator Alex_AeleneiAlex Aelenei Ioan Alex_Aelenei Data 16 martie 2020 20:45:35
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <cstdio>
#include <algorithm>

using namespace std ;

const long long NMAX = 1e5 , INF = 1e18 ;
long long v [ NMAX + 5 ] , data [ NMAX + 5 ] ;
long long dpl [ NMAX + 5 ] , dpr [ NMAX + 5 ] ;

int main ()
{
    freopen ( "branza.in" , "r" , stdin ) ;
    freopen ( "branza.out" , "w" , stdout ) ;

    long long n , s , t , i ;
    unsigned long long ans = 0 ;

    scanf ( "%lld%lld%lld" , & n , & s , & t ) ;

    for ( i = 0 ; i < n ; ++ i )
    {
        scanf ( "%lld%lld" , & v [ i ] , & data [ i ] ) ;
        v [ i ] += s * ( n - i ) ;
    }

    for ( i = 0 ; i < n ; ++ i )
        if ( i % t == 0 )
            dpl [ i ] = v [ i ] ;
        else
            dpl [ i ] = min ( dpl [ i - 1 ] , v [ i ] ) ;

    dpr [ n ] = INF ;
    for ( i = n - 1 ; i >= 0 ; -- i )
        if ( i % t == t - 1 )
            dpr [ i ] = v [ i ] ;
        else
            dpr [ i ] = min ( dpr [ i + 1 ] , v [ i ] ) ;

    for ( i = 0 ; i < t ; ++ i )
        ans += 1LL * data [ i ] * ( dpl [ i ] - s * ( n - i ) ) ;

    for ( i = t ; i < n ; ++ i )
    {
        long long val = min ( dpr [ i - t ] , dpl [ i ] ) ;
        ans += 1LL * data [ i ] * ( val - s * ( n - i ) ) ;
    }

    printf ( "%llu" , ans ) ;

    return 0 ;
}