Cod sursa(job #2306187)

Utilizator rares404AlShaytan - Balasescu Rares rares404 Data 21 decembrie 2018 18:54:55
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.61 kb
#include <bits/stdc++.h>
const int MV(1e5 + 5) ;
int v[MV], dq[MV], ans ;
int main() {
    freopen("branza.in", "r", stdin) ;
    freopen("branza.out", "w", stdout) ;
    int n, s, t, p ;
    scanf("%d %d %d", &n, &s, &t) ;
    register int i ;
    int st(0), dr(-1) ;
    for (i = 1 ; i <= n ; ++ i) {
        scanf("%d %d", v + i, &p) ;
        if (dq[st] == i - t - 1) {
           st ++ ; }
        while (st <= dr && v[i] <= v[dq[dr]] + (i - dq[dr]) * s) {
           dr -- ; }
        dq[++ dr] = i ;
        ans += p * (v[dq[st]] + (i - dq[st]) * s) ; }
    printf("%d", ans) ;
    return 0 ; }