Cod sursa(job #2887295)

Utilizator DafinaTrufasTrufas Dafina DafinaTrufas Data 9 aprilie 2022 11:59:15
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.67 kb
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;

struct sapt{
    int p, c;
} v[100000];

deque <int> dq;

int main()
{int n, s, t, i, cost = 0;
ifstream f("branza.in");
ofstream g("branza.out");
f >> n >> s >> t;
for(i = 0; i < n; i++)
{
    f >> v[i].p >> v[i].c;
    while(!dq.empty() &&  i - dq.front() > t)
        dq.pop_front();
    while(!dq.empty() && v[dq.back()].p * v[dq.back()].c + v[i].p * v[i].c < v[dq.back()].p * (v[dq.back()].c + v[i].c) + s * (i - dq.back()) * v[i].c)
        dq.pop_back();
    dq.push_back(i);
    cost += v[dq.front()].p * v[i].c + (i - dq.front()) * s * v[i].c;
}
g << cost;
return 0;
}