Pagini recente » Cod sursa (job #1491684) | Cod sursa (job #416675) | Cod sursa (job #2147667) | Cod sursa (job #353428) | Cod sursa (job #68445)
Cod sursa(job #68445)
using namespace std;
#define MAX_N 100005
#define ll long long
#include <stdio.h>
typedef struct
{
ll c;
ll p;
} data;
FILE *fin=fopen("branza.in","r"),
*fout=fopen("branza.out","w");
int n,s,t,i,li,lf;
data a[MAX_N];
int m[MAX_N];
int deq[MAX_N];
ll sol;
void includ(int i)
{
int j,vl;
deq[lf++]=i;
j=lf-1;
vl=a[j+1].c+(n-j-1)*s;
while (j>li && vl<=a[j].c+(n-j)*s)
{ deq[j-1]=deq[j]; j--; }
while (i-deq[li]>t) li++;
}
void solve (void)
{
int i;
for (i=1; i<=n; i++)
{
includ(i);
m[i]=a[deq[li]].c+(n-deq[li])*s-(n-i)*s;
sol+=(long long)m[i]* (long long)a[i].p;
}
fprintf(fout,"%lld",sol);
}
int main()
{
fscanf(fin,"%d %d %d",&n,&s,&t);
for (i=1; i<=n; i++)
fscanf(fin,"%lld %lld",&a[i].c,&a[i].p);
solve();
fclose(fin);
fclose(fout);
return 0;
}