Pagini recente » Cod sursa (job #1210981) | Cod sursa (job #2853691) | Cod sursa (job #766357) | Cod sursa (job #697967) | Cod sursa (job #1294268)
#include <stdio.h>
using namespace std;
#define MAX 5000000
long long sum=0;
int dq[MAX+1], top=0, bot=1;
int v[MAX+1];
int main()
{
FILE *fin, *fout;
fin = fopen ("deque.in","r");
fout = fopen("deque.out","w");
int n, k, i, x,cost,y;
fscanf (fin, "%d%d%d", &n,&cost,&k);
fscanf(fin, "%d%d", &v[1],&y);
dq[++top]=1;
for(i=2; i<=n; i++)
{
fscanf(fin, "%d%d", &v[i],&y);
// if(v[dq[top]]>v[i])
//{
while(top >=bot && v[dq[top]]+(i-dq[top])*cost>v[i])
top--;
dq[++top]=i;
// }
// else
// dq[++top]=i;
if(dq[bot] == i-k)
bot++;
if(i >= k)
sum+=v[dq[bot]]*y+(i-dq[top])*cost;
}
fprintf(fout, "%lld", sum);
return 0;
}