Cod sursa(job #2456637)

Utilizator dragomirmanuelDragomir Manuel dragomirmanuel Data 14 septembrie 2019 22:48:01
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.93 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");

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

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

    return false;
}

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

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

    for(int 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;
}