比赛 10101115 评测结果 AAAAAAAAAA
题目名称 矩形分割 最终得分 100
用户昵称 Citron酱 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2010-11-15 08:45:09
显示代码纯文本
#include <fstream>
#include <cstdlib>

#define I_F "cut.in"
#define O_F "cut.out"
#define MAX 2000

using namespace std;

int s[MAX*2];
bool f[MAX*2];
long ans;
short n,m;

void Input();
void swap(short a, short b);
void Qsort(short l, short r);
void Imitate();
void Output();

int main()
{
	Input();
	Qsort(0,m+n-3);
	Imitate();
	Output();
	return 0;
}

void Input()
{
	ifstream fin(I_F);
	fin>>n>>m;
	short i;
	for (i=0; i<n-1; i++)
	{
		fin>>s[i];
		f[i]=true;
	}
	for (; i<m+n-2; i++)
	{
		fin>>s[i];
		f[i]=false;
	}
	fin.close();
}

void swap(short a, short b)
{
	int ts=s[a];
	bool tf=f[a];
	s[a]=s[b];
	f[a]=f[b];
	s[b]=ts;
	f[b]=tf;
}

void Qsort(short l, short r)
{
	int x=s[l+rand()%(r-l+1)];
	int i=l, j=r;
	do
	{
		while (s[i]>x)
			i++;
		while (s[j]<x)
			j--;
		if (i<=j)
			swap(i++,j--);
	} while (i<j);
	if (i<r)
		Qsort(i,r);
	if (l<j)
		Qsort(l,j);
}

void Imitate()
{
	int s1=1, s2=1;
	int i;
	for (i=0; i<m+n-2; i++)
		if (f[i])
		{
			ans+=s[i]*s1;
			s2++;
		}
		else
		{
			ans+=s[i]*s2;
			s1++;
		}
}

void Output()
{
	ofstream fout(O_F);
	fout<<ans<<'\n';
	fout.close();
}