Cod sursa(job #2714458)
| Utilizator | Data | 1 martie 2021 20:16:27 | |
|---|---|---|---|
| Problema | Branza | Scor | 0 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva de probleme | Marime | 0.61 kb |
#include <fstream>
using namespace std;
ifstream fin("branza.in");
ofstream fout("branza.out");
const int N_MAX = 1e5;
int v[N_MAX + 1], dq[N_MAX + 1];
int main()
{
int n, s, t, c, st, dr;
long long rez;
fin >> n >> s >> t;
t++;
rez = 0;
st = 0;
dr = -1;
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 += c * (v[dq[st]] + (i - dq[st]) * s);
}
fout << rez;
return 0;
}
