Cod sursa(job #829346)
| Utilizator | Data | 5 decembrie 2012 09:45:12 | |
|---|---|---|---|
| Problema | Branza | Scor | 100 |
| Compilator | cpp | Status | done |
| Runda | Arhiva de probleme | Marime | 0.52 kb |
#include <fstream>
#define DIM 100002
using namespace std;
ifstream f("branza.in");
ofstream g("branza.out");
long long n, s, t, v[DIM], sol, p, u, i, x[DIM], y[DIM];
int main(){
f>>n>>s>>t;
for(i=1; i<=n; i++)
f>>x[i]>>y[i];
f.close();
p=1;
for(i=1; i<=n; i++)
{
while(v[p]+t<i)
p++;
while( p<=u && x[i]<= ( x[ v[u] ]+( i-v[u] )*s ) )
u--;
v[++u]=i;
sol+=y[i]*( x[ v[p] ]+( i-v[p] )*s );
}
g<<sol<<"\n";
g.close();
return 0;
}
