Cod sursa(job #1742531)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 16 august 2016 16:13:00
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.7 kb
#include <fstream>
#include <vector>
#include <deque>
using namespace std;

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

deque<pair<int, int> > Deque;

int main() {
    int n, s, t;
    cin >> n >> s >> t;
    long long answer = 0;
    for (int i = 1; i <= n; i++) {
        int c, p;
        cin >> c >> p;
        if (Deque.front().second < i - t)
            Deque.pop_front();
        while (!Deque.empty() && c <= (i - Deque.back().second) * s + Deque.back().first)
            Deque.pop_back();
        Deque.push_back(make_pair(c, i));
        answer = answer + 1LL * p * ((i - Deque.front().second) * s + Deque.front().first);
    }
    cout << answer;
    return 0;
}