Cod sursa(job #2320843)

Utilizator raduiliaRadu Vlad Ilia raduilia Data 15 ianuarie 2019 10:36:54
Problema Branza Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <fstream>

using namespace std;

ifstream fin( "branza.in" );
ofstream fout( "branza.out" );

const int               N = 100000;

long long             dq[ N ], c[ N ];
long long       nr[ N ];

int main()
{
    long long             n = 0, s = 0, t = 0, st = 0, dr = -1, x = 0;
    long long       suma = 0;
    t++;
    fin >> n >> s >> t;

    for( int i = 0; i < n; ++i )
    {
        fin >> c[ i ] >> nr[ i ];
    }
    for( int i = 0; i < n; ++i )
    {
        if( st <= dr && dq[ st ] == i - t )
        {
            ++st;
        }
        while( st <= dr && c[ i ] <= c[ dq [ dr ] ] + ( i - dq[ dr ] ) * s )
            --dr;
        dq[ ++dr ] = i;
        suma += (c[ dq[ st ] ] + ( i -dq[ st ] ) * s) * nr[i];

    }
    fout << suma;
    return 0;
}