Nu aveti permisiuni pentru a descarca fisierul grader_test14.ok
Cod sursa(job #382179)
| Utilizator | Data | 13 ianuarie 2010 09:09:29 | |
|---|---|---|---|
| Problema | Branza | Scor | 0 |
| Compilator | cpp | Status | done |
| Runda | Arhiva de probleme | Marime | 0.62 kb |
#include <fstream>
using namespace std;
ifstream in("branza.in");
ofstream out("branza.out");
int c[1<<17],p[1<<17],dq[1<<17];
int n,s,t,i,st=1,dr=0,sum;
inline void stanga(int i){
if(i-t>0 && dq[st]==i-t){
st++;
}
}
void dreapta(int i){
while ( st<=dr && c[i]<=c[dq[dr]]+s*(i-dq[dr])){
dr--;
}
dq[++dr]=i;
}
int main(){
in>>n>>s>>t;
sum=0;
for(i=1;i<=n;i++){
in>>c[i]>>p[i];
}
for(i=1;i<=n;i++){
stanga(i);
dreapta(i);
sum=sum+p[i]*(c[dq[st]]+s*(i-dq[st]));
}
out<<sum;
in.close();
out.close();
return 0;
}
