Cod sursa(job #1906949)

Utilizator ShutterflyFilip A Shutterfly Data 6 martie 2017 17:09:15
Problema Branza Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.65 kb
#include<fstream>
#include<deque>
using namespace std;
ifstream fin("branza.in");
ofstream fout("branza.out");
int n, s, t, c[100005], p[100005];
long long sol = 0;
deque<int> d;
int main(){
    fin >> n >> s >> t;
    for( int i = 1; i <= n; i++ ){
        fin >> c[i] >> p[i];
    }
    for( int i = 1; i <= n; i++ ){
        while( !d.empty() && c[ d.back() ] + s * ( i - d.back() ) > c[i] ){
            d.pop_back();
        }
        d.push_back( i );
        if( i - d.front() == t ){
            d.pop_front();
        }
        sol += 1LL * ( c[ d.front() ] + s * ( i - d.front() ) ) * p[i];
    }
    fout << sol;
    return 0;
}