记录编号	32066	评测结果	AAAAAAAAAAA
题目名称	[POI 1997] 汽油花费	最终得分	100
用户昵称	Truth.Cirno	是否通过	通过
代码语言	C++	运行时间	0.212 s
提交时间	2011-11-05 11:28:00	内存使用	7.89 MiB

#include <cstdio>
using namespace std;

int pri[1000000]={0},dis[1000001]={0};

int main(void)
{
	freopen("pal.in","r",stdin);
	freopen("pal.out","w",stdout);
	int i=0,j=0,n=0,room=0,rest=0,cost=0,minpri=0,minpos=0;
	bool found=false;
	scanf("%d\n%d\n",&room,&n);
	for (i=0;i<n;i++)
	{
		scanf("%d %d\n",&pri[i],&dis[i+1]);
		if (i!=0)
			dis[i+1]+=dis[i];
	}
	for (i=0;i<n;i=minpos)
	{
		found=false;
		for (j=i+1;j<=n;j++)
		{
			if (dis[j]-dis[i]>room)
				break;
			if (pri[j]<=pri[i])
			{
				found=true;
				minpos=j;
				break;
			}
		}
		if (found)
		{
			cost+=pri[i]*(dis[minpos]-dis[i]-rest);
			rest=0;
		}
		else
		{
			minpri=2000000000;
			for (j=i+1;j<=n;j++)
			{
				if (dis[j]-dis[i]>room)
					break;
				if (pri[j]<minpri)
				{
					minpri=pri[j];
					minpos=j;
				}
			}
			cost+=pri[i]*(room-rest);
			rest=room-(dis[minpos]-dis[i]);
		}
	}
	printf("%d\n",cost);
	fclose(stdin);
	fclose(stdout);
	return(0);
}