Cod sursa(job #2714458)

Utilizator davidenko22Stancu David-Andrei davidenko22 Data 1 martie 2021 20:16:27
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.61 kb
#include <fstream>

using namespace std;

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

const int N_MAX = 1e5;

int v[N_MAX + 1], dq[N_MAX + 1];

int main()
{
    int n, s, t, c, st, dr;
    long long rez;
    fin >> n >> s >> t;
    t++;
    rez = 0;
    st = 0;
    dr = -1;
    for ( int i = 1; i <= n; i++ ) {
      fin >> v[i] >> c;
      if ( st <= dr && dq[st] == i - t )
        st++;
      while ( st <= dr && v[dq[dr]] + (i - dq[dr]) * s >= v[i] )
        dr--;
      dq[++dr] = i;
      rez += c * (v[dq[st]] + (i - dq[st]) * s);
    }
    fout << rez;
    return 0;
}