记录编号	422002	评测结果	AAAAAAAAAA
题目名称	[UVa 11292] 勇者斗恶龙	最终得分	100
用户昵称	joel	是否通过	通过
代码语言	C++	运行时间	0.014 s
提交时间	2017-07-08 17:28:21	内存使用	0.54 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstdlib>
using namespace std;
const int M=20000;
int calv[M+10],drag[M+10],y[M+10];
int n,m,kill,cost;
void qsorts(int l,int r,int x[])
{
	if(l==r)
		return ;
	int mid=x[l+rand()%(r-l+1)];
	int ll=l,rr=r;
	do
	{
		while(x[ll]<mid)
			ll++;
		while(x[rr]>mid)
			rr--;
		if(ll<=rr)
		{
			swap(x[ll],x[rr]);
			ll++;
			rr--;
		}
	}while(ll<=rr);
	if(l<rr)
		qsorts(l,rr,x);
	if(ll<r)
		qsorts(ll,r,x);
}
void merge(int l,int r,int x[])
{
	if(l==r)
		return ;
	int mid=(l+r)>>1;
	merge(l,mid,x);
	merge(mid+1,r,x);
	int ll=l,rr=mid+1,p=ll;
	while(ll<=mid&&rr<=r)
	{
		if(x[ll]>x[rr])
			y[p++]=x[rr++];
		else
			y[p++]=x[ll++];
	}
	while(ll<=mid)
		y[p++]=x[ll++];
	while(rr<=r)
		y[p++]=x[rr++];
	for(int i=l;i<=r;i++)
		x[i]=y[i];
}
void prints(int a[],int len)
{
	for(int i=1;i<=len;i++)
		printf("%d ",a[i]);
	printf("\n");
}
int main()
{
	freopen("DragonUVa.in","r",stdin);
	freopen("DragonUVa.out","w",stdout);
	scanf("%d%d",&n,&m);
	if(n==0&&m==0)
	{
		printf("0\n");
		return 0;
	}
	for(int i=1;i<=n;i++)
		scanf("%d",&drag[i]);
	for(int j=1;j<=m;j++)
		scanf("%d",&calv[j]);
	merge(1,n,drag);
	qsorts(1,m,calv);
	int f=1;
	for(int i=1;i<=n;i++)
	{
		for(int j=f;j<=m;j++)
		{
			if(calv[j]>=drag[i])
			{
				cost+=calv[j];
				f=j+1;
				kill++;
				break;
			}
		}
	}
	if(kill==n)
		printf("%d\n",cost);
	else
		printf("Loowater is doomed\n");
	return 0;
}