Cod sursa(job #1139409)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 11 martie 2014 09:20:15
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.69 kb
#include<fstream>
#include<deque>

using namespace std;

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

typedef long long i64;

const int nmax = 100000;
int c[ nmax + 1 ];

deque <int> d;

int main()
{
    int n, p, s, t;
    i64 sol;
    fin>>n>>s>>t;
    sol = 0;
    for( int i = 0; i < n; ++ i ) {
        fin>>c[i]>>p;
        while ( !d.empty() && c[i] < c[ d.back() ] + s * (i - d.back()) ) {
            d.pop_back();
        }
        if ( !d.empty() && d.front() < i - t ) {
            d.pop_front();
        }
        d.push_back( i );
        sol += (i64)( c[ d.front() ] + s * (i - d.front()) ) * p;
    }
    fout<<sol<<'\n';
    fin.close();
    fout.close();
    return 0;
}