Cod sursa(job #1106007)

Utilizator Athena99Anghel Anca Athena99 Data 12 februarie 2014 12:40:31
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.65 kb
#include <deque>
#include <fstream>

using namespace std;

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

typedef long long i64;

const int nmax= 100000;

deque <int> deq;
int c[nmax+1], p;

int main(  ) {
    int n, s, t;
    fin>>n>>s>>t;

    i64 sol= 0;
    for ( int i= 1; i<=n; ++i ) {
        fin>>c[i]>>p;
        while ( !deq.empty() && c[i]<c[deq.back()]+s*(i-deq.back()) ) {
            deq.pop_back();
        }
        if ( !deq.empty() && deq.front()<i-t ) {
            deq.pop_front();
        }

        deq.push_back(i);
        sol= (i64)(sol+(i64)( c[deq.front()]+s*( i-deq.front() ) )*p);
    }

    fout<<sol<<"\n";

    return 0;
}