Cod sursa(job #2085159)

Utilizator andreicoman299Coman Andrei andreicoman299 Data 9 decembrie 2017 19:27:34
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.72 kb
#include <bits/stdc++.h>
#define MAXN 100000

struct A{
    long long p, c;
}v[1 + MAXN];
int dq[1 + MAXN], p, u;
int main(){
    FILE*fi,*fo;
    fi=fopen("branza.in","r");
    fo=fopen("branza.out","w");

    int n, s, t;
    fscanf(fi,"%d%d%d", &n, &s, &t);
    long long cost = 0;
    p = 0;
    u = -1;
    for(int i = 1; i <= n; i++){
        fscanf(fi,"%lld%lld", &v[i].c, &v[i].p);
        v[i].c -= i * s;
        while(p <= u && i - dq[p] > t)
            p++;
        while(u >= p && v[i].c < v[dq[u]].c)
            u--;
        u++;
        dq[u] = i;
        cost = cost + (v[dq[p]].c + s * i) * v[i].p;
    }
    fprintf(fo,"%lld", cost);

    fclose(fi);
    fclose(fo);
    return 0;
}