Cod sursa(job #3371905)

Utilizator cosminteoaTeodorescu Cosmin cosminteoa Data 1 noiembrie 2026 17:40:17
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.62 kb
#include <bits/stdc++.h>
#define NMAX 1000000
using namespace std;
int c[NMAX + 5];
int p[NMAX + 5];
deque <int> dq;
int main()
{
    ifstream fin( "branza.in" );
    ofstream fout( "branza.out" );
    int n, s, t, i, cost;
    fin >> n >> s >> t;
    cost = 0;
    for( i = 1; i <= n; i++ ){
      fin >> c[i] >> p[i];
      while( !dq.empty() && c[dq.back()] + s * ( i - dq.back() ) >= c[i] )
        dq.pop_back();
      dq.push_back(i);
      if( dq.front() < i - t )
        dq.pop_front();
      cost += ( c[dq.front()] + s * ( i - dq.front() ) ) * p[i];
    }
    fout << cost << '\n';
    return 0;
}