Pagini recente » Cod sursa (job #2913157) | Cod sursa (job #1467456) | Cod sursa (job #2160390) | Cod sursa (job #550879) | Cod sursa (job #111772)
Cod sursa(job #111772)
#include <cstdio>
#define INF "branza.in"
#define OUF "branza.out"
#define NMAX 100002
using namespace std;
struct sapt
{
long long k,cost;
}a[NMAX];
int main()
{
FILE *in,*out;
in=fopen(INF,"r");
out=fopen(OUF,"w");
long long i,n,s,t,p,q,id[NMAX];
long long total,kg;
fscanf(in,"%lld%lld%lld",&n,&s,&t);
fscanf(in,"%lld%lld",&a[1].cost,&a[1].k);
p=1;q=1;id[p]=1;
total=a[1].k*a[1].cost;
//printf("%lld %lld\n",a[1].k,a[p].cost);
for(i=2;i<=n;++i)
{
fscanf(in,"%lld%lld",&a[i].cost,&a[i].k);
if(i-id[p]>t) ++p;
++q;
while(q>p&&a[i].cost<(i-id[q-1])*s+a[id[q-1]].cost) --q;
id[q]=i;
kg=(i-id[p])*s+a[id[p]].cost;
total+=a[i].k*kg;
//printf("%lld %lld %lld\n",a[i].k,a[id[p]].cost,(i-id[p])*s);
}
fprintf(out,"%lld\n",total);
fclose(in);fclose(out);
return 0;
}