记录编号	21815	评测结果	AAAAAAAAAA
题目名称	498.矩形分割	最终得分	100
用户昵称	wangwangdog	是否通过	通过
代码语言	C++	运行时间	0.008 s
提交时间	2010-11-15 16:29:44	内存使用	0.28 MiB

#include<stdio.h>
long n,m,shu[2001],heng[2001],shui[2001],hengi[2001],mm,nn,i,allheng,allshu,allhengi,allshui;
long long min;
void qsort1 (long a,long b)
{
	long t1=a,t2=b,t3=heng[(a+b)/2];
	do
	{
		while(heng[t1]<t3)t1++;
		while(heng[t2]>t3)t2--;
		if(t1<=t2)
		{
			long o=heng[t1];
			heng[t1]=heng[t2];
			heng[t2]=o;
			t1++;
			t2--;
		}
	}
	while(t1<t2);
	if(t1<b)qsort1(t1,b);
	if(t2>a)qsort1(a,t2);
}
void qsort2 (long a,long b)
{
	long t1=a,t2=b,t3=shu[(a+b)/2];
	do
	{
		while(shu[t1]<t3)t1++;
		while(shu[t2]>t3)t2--;
		if(t1<=t2)
		{
			long o=shu[t1];
			shu[t1]=shu[t2];
			shu[t2]=o;
			t1++;
			t2--;
		}
	}
	while(t1<t2);
	if(t1<b)qsort2(t1,b);
	if(t2>a)qsort2(a,t2);
}
FILE *fin,*fout;
int main()
{
	fin=fopen("cut.in","rb");
	fout=fopen("cut.out","wb");
	fscanf(fin,"%ld%ld\n",&n,&m);
	for(i=1;i<=n-1;i++)
	{
		fscanf(fin,"%ld",&heng[i]);
	}
	fscanf(fin,"\n");
	for(i=1;i<=m-1;i++)
	{
		fscanf(fin,"%ld",&shu[i]);
	}
	qsort1(1,n-1);
	qsort2(1,m-1);
	nn=n-1;
	mm=m-1;
	min=0;
	while(nn>0||mm>0)
	{
		if(heng[nn]>shu[mm]||mm==0)
		{
			min=min+(m-mm)*heng[nn];
			nn--;
		}
		else
		{
		if(heng[nn]<=shu[mm]||nn==0)
		{
			min=min+(n-nn)*shu[mm];
			mm--;
		}
		}
	}
	fprintf(fout,"%ld",min);
	fclose(fin);
	fclose(fout);
	return 0;
}