Cod sursa(job #2708811)
| Utilizator | Data | 19 februarie 2021 14:24:34 | |
|---|---|---|---|
| Problema | Branza | Scor | 100 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva de probleme | Marime | 0.64 kb |
#include <bits/stdc++.h>
using namespace std;
ifstream fin("branza.in");
ofstream fout("branza.out");
int v[100100], dq[100100];
int st = 0, dr = -1;
long long rez = 0;
int n, s, t, c;
int main()
{
fin >> n >> s >> t;
t++;
for (int i = 1; i <= n; i++)
{
fin >> v[i] >> c;
if (st <= dr && dq[st] == i - t)
{
st++;
}
while (st <= dr && v[dq[dr]] + (i - dq[dr])*s >= v[i])
{
dr--;
}
dq[++dr] = i;
rez += (long long)c * (v[dq[st]] + (long long)(i - dq[st]) * s);
}
fout << rez;
return 0;
}
