Cod sursa(job #2456638)

Utilizator dragomirmanuelDragomir Manuel dragomirmanuel Data 14 septembrie 2019 22:49:46
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <deque>

using namespace std;

const long long NMax = (long long)1e5+10;
ifstream fin("branza.in");
ofstream fout("branza.out");

long long C[NMax], P[NMax];
deque < long long > dq;

bool betterPrice(long long i, long long j, long long S){
    if(S * (i-j) + C[j] >= C[i]){
        return true;
    }

    return false;
}

int main()
{
    long long N, S, T; fin >> N >> S >> T;
    for(long long i=1; i<=N; i++){
        fin >> C[i] >> P[i];
    }

    long long sum = C[1] * P[1];
    dq.push_back(1);

    for(long long i=2; i<=N; i++){
            if(i - dq.front() > T){
                dq.pop_front();
            }

            while(!dq.empty() && betterPrice(i, dq.back(), S)){
                dq.pop_back();
            }

            dq.push_back(i);
            sum += 1LL * C[dq.front()] * P[i] + P[i] * (i - dq.front()) * S;
    }

    fout << sum;

    return 0;
}