Cod sursa(job #1718583)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 18 iunie 2016 13:32:39
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <bits/stdc++.h>
using namespace std;
typedef long long i64;

const int NMAX = 100005;

struct PII {
    int x, y;

    inline PII() { }
    inline PII(int _x, int _y) {
        x = _x;
        y = _y;
    }
};

PII v[NMAX];

int main(void) {
    freopen("branza.in", "r", stdin);
    freopen("branza.out", "w", stdout);
    int n, s, t, c, p;
    i64 ans;
    deque<PII> dq;

    ans = 0;

    scanf("%d%d%d",&n,&s,&t);
    for(int i=1; i<=n; ++i) {
        scanf("%d%d",&c,&p);

        while(!dq.empty() && i-dq.front().y>t)
            dq.pop_front();
        while(!dq.empty() && (i-dq.back().y)*s+dq.back().x>=c)
            dq.pop_back();
        dq.push_back(PII(c, i));

        ans+=i64((i-dq.front().y)*s+dq.front().x)*p;
    }

    printf("%lld\n",ans);

    fclose(stdin);
    fclose(stdout);
    return 0;
}