Cod sursa(job #2060770)
| Utilizator | Data | 8 noiembrie 2017 18:16:51 | |
|---|---|---|---|
| Problema | Branza | Scor | 100 |
| Compilator | cpp | Status | done |
| Runda | Arhiva de probleme | Marime | 0.6 kb |
#include <iostream>
#include <fstream>
using namespace std;
int main()
{
int i, n, t, s, st, dr, c[100000], p[100000], d[100000];
long long sum=0;
ifstream f ("branza.in");
ofstream g ("branza.out");
f>>n>>s>>t;
t++;
for (i=0; i<n; i++) f>>c[i]>>p[i];
st=0;
dr=-1;
for (i=0; i<n; i++)
{
if (st<=dr && d[st]==i-t)
{
st++;
}
while (st<=dr && c[i]<=c[d[dr]]+s*(i-d[dr]))
{
dr--;
}
d[++dr]=i;
sum += p[i] * (c[d[st]] + (long long)s*(i - d[st]));
}
g<<sum;
return 0;
}
