Cod sursa(job #1495529)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 3 octombrie 2015 11:10:53
Problema Branza Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.7 kb
#include <bits/stdc++.h>

using namespace std;

const int Nmax = (int) 1e5;

int cost[Nmax + 1];
deque <int> d;

int main()
{
    ifstream in("branza.in");
    ofstream out("branza.out");
    int n, s, t;
    int c;
    long long res;

    in >> n >> s >> t;
    res = 0;
    for ( int i = 1; i <= n; i++ )
    {
        in >> cost[i] >> c;
        while ( !d.empty() && 1LL * cost[i] * c < 1LL * cost[d.back()] * c + 1LL * s * c * ( i - d.back() ) )
            d.pop_back();
        d.push_back(i);
        if ( d.front() == i - t )
            d.pop_front();
        res += 1LL * cost[d.front()] * c + 1LL * s * c * ( i - d.front() );
    }
    in.close();

    out << res << '\n';
    out.close();
    return 0;
}