Cod sursa(job #1106005)

Utilizator Athena99Anghel Anca Athena99 Data 12 februarie 2014 12:39:24
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.63 kb
#include <deque>
#include <fstream>

using namespace std;

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

const int nmax= 100000;

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

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

    int 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= sol+p*( c[deq.front()]+s*( i-deq.front() ) );
    }

    fout<<sol<<"\n";

    return 0;
}