Cod sursa(job #2490957)

Utilizator daria_stoianStoian Daria Alexandra daria_stoian Data 11 noiembrie 2019 15:30:04
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.82 kb
#include <stdio.h>
#include <iostream>

const int N = 100001;

using namespace std;

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

int main(){
    FILE *fin, *fout;
    fin = fopen( "branza.in", "r" );
    fout = fopen( "branza.out", "w" );
    long long n, t, st, dr, s, i, rez;
    rez = 0;
    fscanf( fin, "%lld%lld%lld", &n, &s, &t );
    for (  i = 1; i <= n; i ++ ){
        fscanf( fin, "%lld%lld", &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];
        //fprintf(fout, "%d -> %d\n", i, rez);
    }
    fprintf( fout, "%lld", rez );
    fclose( fin );
    fclose( fout );
    return 0;
}