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

#include<iostream>
#include<fstream>
#include<cstdlib>
using namespace std;
long long sum=0;
void qst(int a[],int left,int right)
{
	int i=left,j=right,mid,t;
	mid=a[(rand()%(right-left+1))+left];
	do
	{
		while(i<right&&a[i]>mid)
			i++;
		while(j>left&&a[j]<mid)
			j--;
		if(i<=j)
		{
			t=a[i];
			a[i]=a[j];
			a[j]=t;
			i++;
			j--;
		}
	}
	while(i<=j);
	if(i<right)
		qst(a,i,right);
	if(j>left)
		qst(a,left,j);
}

int main()
{
	ifstream fin("cut.in");
	ofstream fout("cut.out");
	int cl=1,cr=1,n,m,i,j,row[2001],line[2001];
	fin>>n>>m;
	for(i=1;i<n;i++)
		fin>>row[i];
	for(i=1;i<m;i++)
		fin>>line[i];
	qst(row,1,n-1);
	qst(line,1,m-1);
	i=1; j=1;
	do
	{
		if(row[i]>line[j])
		{
			sum+=row[i]*cr;
			cl++;
			i++;
		}
		else
		{
			sum+=line[j]*cl;
			cr++;
			j++;
		}
	}
	while(i!=n||j!=m);
	fout<<sum<<endl;
	return 0;
}