Submission #1204592

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;

#define int long long

typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define pb push_back
#define fi first
#define se second
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}


int N,M,K;
int A[55],B[55];
typedef bitset<22222*55>bs;

bs dp[60];

signed main(){
    cin>>N>>M>>K;

    rep(i,N)cin>>A[i];
    rep(i,M)cin>>B[i];


    if(K==1){
        int sumA=accumulate(A,A+N,0ll);
        int sumB=accumulate(B,B+M,0ll);
        int ma=0;
        rep(i,N)rep(j,M){
            chmax(ma,(sumA-A[i]+B[j])*(sumB-B[j]+A[i]));
        }
        cout<<ma<<endl;
        return 0;
    }

    chmin(K,N);chmin(K,M);

    int sum=accumulate(A,A+N,0ll);
    dp[0][sum]=1;

    for(int i=0;i<N;i++){
        for(int j=K-1;j>=0;j--){
            dp[j+1]|=dp[j]>>A[i];
        }
    }

    for(int i=0;i<M;i++){
        for(int j=1;j<=K;j++){
            dp[j-1]|=dp[j]<<B[i];
        }
    }

    int ma=0;
    sum+=accumulate(B,B+M,0ll);
    rep(i,22222*55)if(dp[0][i])chmax(ma,i*(sum-i));
    cout<<ma<<endl;
    return 0;
}

Submission Info

Judge Result