Mai intai trebuie sa te autentifici.
Cod sursa(job #915401)
| Utilizator | Data | 14 martie 2013 23:28:23 | |
|---|---|---|---|
| Problema | Branza | Scor | 40 |
| Compilator | cpp | Status | done |
| Runda | Arhiva de probleme | Marime | 0.67 kb |
#include <cstdio>
#include <deque>
#define NMAX 100001
using namespace std;
int n;
long long int S,Smax,T,C[NMAX],P[NMAX];
deque < int >Deque;
int main(){
freopen("branza.in","r",stdin);
freopen("branza.out","w",stdout);
scanf("%d%lld%lld",&n,&S,&T);
for(register int i=1;i<=n;++i){
scanf("%lld%lld",&C[i],&P[i]);
while(!Deque.empty() && C[i] < C[Deque.back()] + S*(i-Deque.back()))
Deque.pop_back();
Deque.push_back(i);
if(Deque.front()+T ==i)
Deque.pop_front();
Smax+=C[Deque.front()]*P[i] + P[i]*S*(i-Deque.front());
}
printf("%lld",Smax);
return 0;
}
