Cod sursa(job #1068731)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 28 decembrie 2013 18:16:09
Problema Branza Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.72 kb
#include <iostream>
#include <fstream>
#include <deque>

using namespace std;

const int Nmax = 100001;

int N;
deque <int> deck;
uint64_t sol;
long long S, T;
long long cost[Nmax], cant[Nmax], V[Nmax];

int main()
{
    ifstream f("branza.in");
    ofstream g("branza.out");

    f >> N >> S >> T;

    for ( int i = 1; i <= N; ++i )
    {
        f >> cost[i] >> cant[i];

        V[i] = cost[i] - 1ULL * i * S;

        while ( deck.size() && V[ deck.back() ] >= V[i] ) deck.pop_back();
        while ( deck.size() && deck.front() <= i - T ) deck.pop_front();

        deck.push_back( i );

        sol += ( V[ deck.front() ] + 1ULL * S * i ) * cant[i];
    }

    g << sol << "\n";

    return 0;
}