记录编号	366185	评测结果	AAAAAAAAAA
题目名称	[HAOI 2009]巧克力	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.514 s
提交时间	2017-01-23 09:22:21	内存使用	4.10 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e5+10;
#define rint register int
typedef long long ll;
int n,m,a[N],b[N];
ll sa[N],sb[N],dp[2][N];
inline ll min(ll x,ll y){return x<y?x:y;}
int main()
{
	freopen("chocolate.in","r",stdin);
	freopen("chocolate.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=1;i<n;i++) scanf("%d",&a[i]);
	for (int i=1;i<m;i++) scanf("%d",&b[i]);
	sort(a+1,a+n);
	reverse(a+1,a+n);
	for (int i=1;i<n;i++) sa[i]=sa[i-1]+a[i];
	sort(b+1,b+m);
	reverse(b+1,b+m);
	for (int j=1;j<m;j++) sb[j]=sb[j-1]+b[j];
	bool x=1,y=0;
	for (int j=0;j<m;j++) dp[x][j]=1e9;
	dp[x][0]=0;
	for (rint i=0;i<n;i++){
		for (rint j=0;j<m;j++) dp[y][j]=1e9;
		for (rint j=0;j<m;j++){
			dp[y][j]=min(dp[y][j],dp[x][j]+a[i+1]+sb[m-1]-sb[j]);
			dp[x][j+1]=min(dp[x][j+1],dp[x][j]+b[j+1]+sa[n-1]-sa[i]);
		}
		swap(x,y);
	}
	printf("%lld\n",dp[x][m-1]);
	return 0;
}