Cod sursa(job #2174661)

Utilizator priboiraduPriboi Radu Bogdan priboiradu Data 16 martie 2018 12:55:33
Problema Branza Scor 40
Compilator c Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <stdio.h>
#include <stdlib.h>
#define INFINIT 20000000

struct deq {
    long long cost, tp;
} dq[100000];

int prim = 0, ultim = 0;

int main() {
    FILE *fin, *fout;
    long long n, s, t, i, c, p, j, ctot = 0LL;
    fin = fopen( "branza.in", "r" );
    fout = fopen( "branza.out", "w" );
    fscanf( fin, "%lld%lld%lld", &n, &s, &t );
    dq[0].cost = INFINIT;
    for ( i = 0; i < n; i++ ) {
        fscanf( fin, "%lld%lld", &c, &p );
        while ( ultim >= 0 && c <= dq[ultim].cost )
            ultim--;
        dq[ultim + 1].cost = c;
        dq[ultim + 1].tp = t;
        ultim++;
        ctot += dq[prim].cost * p;
        for ( j = prim; j <= ultim; j++ ) {
            dq[j].cost += s;
            dq[j].tp--;
        }
        if ( dq[prim].tp == -1 )
            prim++;
    }
    fprintf( fout, "%lld", ctot );
    fclose( fin );
    fclose( fout );
    return 0;
}