Cod sursa(job #1391297)
Utilizator | Catruna Andy AndyCatruna | Data | 17 martie 2015 19:59:45 |
---|---|---|---|
Problema | Branza | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.55 kb |
#include <fstream>
#define dim 100005
using namespace std;
ifstream fin("branza.in");
ofstream fout("branza.out");
int n,c[dim],P[dim],m[dim],d[dim],s,t,i,p,u,S;
int main(){
fin>>n>>s>>t;
for(i=1;i<=n;i++){
fin>>c[i]>>P[i];
}
S+=c[1]*P[1];
d[1]=1;
p=1;u=1;
for(i=2;i<=n;i++){
while(p<=u && c[i]<=c[d[u]]+(i-d[u])*s){
u--;
}
d[++u]=i;
if(i-d[p]==t){
p++;
}
S+=(c[d[p]]+(i-d[p])*s)*P[i];
}
fout<<S<<"\n";
return 0;
}