Submission #1723697

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
typedef pair<double,int>Q;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
bitset<22223*55>dp[2][56],dp2[2][56];
int n,m,k,a[56],b[56];
int hoge[22223*55],sum;
int main(){
	cin>>n>>m>>k;
	rep(i,n)cin>>a[i],sum+=a[i];
	rep(i,m)cin>>b[i],sum+=b[i];
	int cur=0,nxt=1;
	dp[0][0].set(0);
	rep(i,n){
		rep(j,56) dp[nxt][j].reset();
		for(int j=0;j<=i;j++){
			dp[nxt][j] |= dp[cur][j];
			dp[nxt][j+1] |= dp[cur][j]<<a[i];
		}
		swap(cur,nxt);
	}
	int cur2=0,nxt2=1;
	dp2[0][0].set(0);
	rep(i,m){
		rep(j,56) dp2[nxt2][j].reset();
		for(int j=0;j<=i;j++){
			dp2[nxt2][j] |= dp2[cur2][j];
			dp2[nxt2][j+1] |= dp2[cur2][j]<<b[i];
		}
		swap(cur2,nxt2);
	}
	//cout<<dp[cur][1][2]<<dp[cur][1][3]<<dp[cur][2][4]<<dp[cur][2][5]<<dp[cur][3][7]<<endl;
	ll ans = 0;
	for(int i=0;i<=min(min(m,n),k);i++){
		if(k==1 && i==0) continue;
		int nxt = 0;
		for(int j=0;j<22223*55;j++){
			if(dp[cur][n-i][j]) hoge[nxt++] = j;
		}
		//for(int i=0;i<nxt;i++) cout<<hoge[i]<<" ";
		int curr = sum/2;
		nxt--; int up = nxt;
		for(int j=0;j<22223*55;j++){
			if(dp2[cur2][i][j]){
			    //cout<<j<<endl;
				while(nxt>0 && hoge[nxt]>=curr-j) nxt--;
				//dp[cur][n-i][hoge-j]
				for(int f=max(0,nxt-2);f<=min(up,nxt+2);f++){
					ans = max(ans,1LL*(sum-hoge[f]-j)*(hoge[f]+j));
				}
			}
		}
	}
	cout<<ans<<endl;
}

Submission Info

Judge Result