Cod sursa(job #1943265)
Utilizator | Moanta Ionut Liviu Liviu_Ionut_Moanta | Data | 28 martie 2017 14:38:19 |
---|---|---|---|
Problema | Branza | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.54 kb |
#include<fstream>
using namespace std;
ifstream fin("branza.in");
ofstream fout("branza.out");
int n,s,t,i,p1,u,q;
int c[100003],p[100003],v[100003];
int main(){
fin>>n>>s>>t;
for(i=1;i<=n;i++){
fin>>c[i]>>p[i];
}
v[1]=1;
p1=1;
u=1;
q=c[1]*p[1];
for(i=2;i<=n;i++){
while(p1<=u&&c[i]<=c[v[u]]+s*(i-v[u])){
u--;
}
v[++u]=i;
if(i-v[p1]==t+1){
p1++;
}
q+=(c[v[p1]]+(i-v[p1])*s)*p[i];
}
fout<<q;
return 0;
}