Cod sursa(job #2732332)

Utilizator faalaviaFlavia Podariu faalavia Data 28 martie 2021 21:42:37
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.62 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream fin ("branza.in");
ofstream fout ("branza.out");

int main()
{
    int n, s, t, i, total = 0;
    fin >> n >> s >> t;
    int c[n+5], p, deq[n+5];
    int frontt = 1, backk = 0;

    for (i = 0; i <n ; i++)
     {
       fin >> c[i] >> p;
       while(frontt <= backk && c[i] <= c[deq[backk]] + s* (i - deq[backk]))
         backk--;
       deq[++backk] = i;

       if(frontt <= backk && (deq[frontt] == i - t - 1))
        frontt++;

       total += p*(c[deq[frontt]] + s*(i- deq[frontt]));
     } 
     fout << total;
    return 0;
}