Cod sursa(job #2153859)

Utilizator Andrei17Andrei Pascu Andrei17 Data 6 martie 2018 15:35:36
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.72 kb
#include <fstream>

using namespace std;

ifstream in("branza.in");
ofstream out("branza.out");

const int N = 100002;

int n, s, t;
long long c[N], p[N], deq[N];

void solve() {
    long long smax = 0;
    int st = 0, dr = -1;

    for (int i = 1; i <= n; i++) {

        if (st <= dr && deq[st] == i - t - 1) {
            st++;
        }

        while (st <= dr && p[ deq[dr] ] + (i - deq[dr]) * s >= p[i]) {
            dr--;
        }
        deq[++dr] = i;

        smax += 1LL * (c[i] * p[ deq[st] ] + c[i] * (i - deq[st]) * s);
    }

    out << smax;
}

int main()
{
    in >> n >> s >> t;
    for (int i = 1; i <= n; i++) in >> p[i] >> c[i];
    in.close();
    solve();
    out.close();
}