Cod sursa(job #1419076)
| Utilizator | Data | 14 aprilie 2015 17:43:33 | |
|---|---|---|---|
| Problema | Branza | Scor | 0 |
| Compilator | cpp | Status | done |
| Runda | Arhiva de probleme | Marime | 0.62 kb |
#include<fstream>
#define f first
#define s second
using namespace std;
ifstream fin("branza.in");
ofstream fout("branza.out");
int d[100005];
unsigned long long c,u,p,k,i,n,cost;
pair<int,int> v[100005];
int main(){
fin>>n>>c>>k;
for(i=1;i<=n;i++){
fin>>v[i].first>>v[i].second;
}
d[1]=p=u=1;
cost=v[1].f*v[1].s;
for(i=2;i<=n;i++){
while(p<=u && v[d[u]].f+(i-d[u])*c*1LL > v[i].f){
u--;
}
d[++u]=i;
if(i-d[u]==k+1){
p++;
}
cost+=(v[d[p]].f+(i-d[p])*c)*v[i].s*1LL;
}
fout<<cost;
return 0;
}
