Cod sursa(job #3250878)

Utilizator SergiuS3003Sergiu Stancu Nicolae SergiuS3003 Data 24 octombrie 2024 00:39:35
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.67 kb
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;
ifstream f ("branza.in");
ofstream g ("branza.out");
const int NMAX = 100001;
int C[NMAX], P[NMAX];
int main()
{
    int N, S, T;
    f >> N >> S >> T;
    long long totalCost = 0;
    deque<int>d;
    for (int i = 1; i <= N; i++)
    {
        f >> C[i] >> P[i];
        while (!d.empty() && (C[d.back()] + (i - d.back()) * S) >= C[i])
            d.pop_back();
        d.push_back (i);
        if (d.front() < i - T)
        {
            d.pop_front();
        }
        totalCost += (C[d.front()] + (i - d.front()) * S) * 1LL * P[i];
    }
    g << totalCost;
    return 0;
}