记录编号	299431	评测结果	AAAAAAAAAAA
题目名称	[POI 1997] 汽油花费	最终得分	100
用户昵称	open the window	是否通过	通过
代码语言	C++	运行时间	0.195 s
提交时间	2016-08-25 16:20:43	内存使用	6.50 MiB

#include<cstdio>
#include<iostream>
using namespace std;
int c[1000001],d[1000001];
int w,n,p,l=1,ans,tot;
int main()
{
	freopen("pal.in","r",stdin);
	freopen("pal.out","w",stdout);
	scanf("%d%d",&w,&n);
	for (int i=1; i<=n; ++i)
	{
		scanf("%d%d",&c[i],&d[i+1]);
		d[i+1]+=d[i];
	}
	while (l<n+1)
	{
		int top=l,minx=99999999,k=0;
		bool f=false;
		while (d[top+1]-d[l]<=w && top<n+1) top++;
		for (int i=l+1; i<=top; ++i)
		 if (c[i]<c[l])
		 {
			if (tot>=(d[i]-d[l])) tot-=(d[i]-d[l]);
			 else 
			 {
			 	ans+=c[l]*(d[i]-d[l]-tot);
			 	tot=0;
			 }
			l=i;
			f=true;
			break;
		 }
		 else if (c[i]<minx)
		 {
		 	minx=c[i];
		 	k=i;
		 }
		if (!f)
		{
			ans+=c[l]*(w-tot);
			tot=w-d[k]+d[l];
			l=k;
		}
	}
	printf("%d\n",ans);
}