Cod sursa(job #2808533)

Utilizator daria_stoianStoian Daria Alexandra daria_stoian Data 25 noiembrie 2021 11:35:33
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.7 kb
  #include <fstream>

  const int N = 100001;

  using namespace std;

  long long c[N], p[N], dq[N];

  int main(){
    ifstream fin( "branza.in" );
    ofstream fout( "branza.out" );
    long long n, t, st, dr, s, i, rez;
    rez = 0;
    fin >> n >> s >> t;
    for (  i = 1; i <= n; i ++ ){
        fin>> c[i] >> p[i];
    }
    st = 1;
    dr = 0;
    for ( i = 1; i <= n; i ++ ){
        if (t + dq[st] < i ){
            st ++;
        }
        while ( dr >= st &&  c[i] <= c[dq[dr]]+(i - dq[dr]) * s ){
            dr --;
        }
        dq[++dr] = i;

        rez+=c[dq[st]]*p[i]+ s*(i-dq[st])*p[i];
    }fout << rez;
    fin.close();
    fout.close();
    return 0;
  }