Cod sursa(job #2071524)
| Utilizator | Data | 20 noiembrie 2017 19:07:26 | |
|---|---|---|---|
| Problema | Branza | Scor | 100 |
| Compilator | cpp | Status | done |
| Runda | Arhiva de probleme | Marime | 0.53 kb |
#include <fstream>
using namespace std;
ifstream in("branza.in");
ofstream out("branza.out");
const int N = 100001;
int d[N],c[N],p[N];
int main()
{
int n,t,i,j,st,dr,s=0;
long long ma=0;
in>>n>>s>>t;
t++;
st=0,dr=-1;
for(i=1;i<=n;i++)
{
in>>c[i]>>p[i];
if (st <= dr && d[st] == i - t)
st++;
while(st<=dr && c[i]<=c[d[dr]]+(long long)s*(i-d[dr]))
dr--;
d[++dr]=i;
ma +=p[i]*(c[d[st]]+(long long)s*(i-d[st]));
}
out<<ma;
return 0;
}
