Cod sursa(job #1491445)

Utilizator andrei_diaconu11Andrei C. Diaconu andrei_diaconu11 Data 25 septembrie 2015 15:10:39
Problema Branza Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <stdio.h>
#include <stdlib.h>

int st, dr, t, s;

struct deck{
    int sap, pret;
} deque[100000];

void stanga(int sp){
    if(sp-deque[st].sap>t)
        st++;
}

void dreapta(int sp, int pr){
    while(dr>=st && pr<=deque[dr].pret+(sp-deque[dr].sap)*s)
        dr--;
    dr++;
    deque[dr].sap=sp;
    deque[dr].pret=pr;
}

int main()
{
    int p, c, n, i;
    long long total;
    FILE *fi=fopen("branza.in", "r"), *fo=fopen("branza.out", "w");
    fscanf(fi, "%d%d%d", &n, &s, &t);
    st=0;
    total=0;
    dr=-1;
    for(i=0;i<n;i++){
        fscanf(fi, "%d%d", &p, &c);
        dreapta(i,p);
        stanga(i);
        total=total+1LL*(deque[st].pret+(i-deque[st].sap)*s)*c;
    }
    fprintf(fo, "%lld", total);
    fclose(fi);
    fclose(fo);
    return 0;
}