比赛 2025.12.6 评测结果 AAAAAAAAAA
题目名称 巧克力 最终得分 100
用户昵称 Yis 运行时间 0.247 s
代码语言 C++ 内存使用 3.73 MiB
提交时间 2025-12-06 11:31:35
显示代码纯文本
#include<bits/stdc++.h>
#include<vector>
using namespace std;
int n,m;
vector<int>lin,row;
int main(){
	freopen("chocolate.in","r",stdin);
	freopen("chocolate.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m;
	lin=vector<int>(n-1);
	row=vector<int>(m-1);
	for(int i=0;i<n-1;cin>>lin[i++]);
	for(int i=0;i<m-1;cin>>row[i++]);
	sort(lin.begin(),lin.end(),greater<int>());
	sort(row.begin(),row.end(),greater<int>());
	vector<int>d1(m,0),d2(m,0);
	for(int j=1;j<=m-1;j++){
		d1[j]=d1[j-1]+row[j-1];
	}
	for(int i=1;i<n;i++){
		d2[0]=d1[0]+lin[i-1];
		for(int j=1;j<=m-1;j++){
			d2[j]=1<<30;
			d2[j]=min(d2[j],d1[j]+lin[i-1]*(j+1));
			d2[j]=min(d2[j],d2[j-1]+row[j-1]*(i+1));
		}
		swap(d1,d2);
	}
	cout<<d1[m-1]<<endl;
	return 0;
}