D. Yet Another Minimization Problem

Portal ：CF

Preface ： After the new year, so many , Lose big points , from 1850 Transfer to 1700, It's really sour . This scene D Of dp It's a wonderful point （ At least I won't ）, I saw Small t After the code , be filled with wisdom （ Small t Such as medicine , Good reading can cure fools ）.

Text ：

First look at the data range , Give it to 2 Second implementation plus n by 100, When I first solved it, I thought it was a problem of violent enumeration , So there is no simplification at all +dp It's like . So I lost a lot of points .

By simplifying the formula , You can get , The best time is

Of course , It's hard to get the most perfect situation , So just get as close as possible .

However, how can we find this optimal sum ？

My initial thought was violence , however MLE 了 （ I am a idiot. ）

The positive solution is through iteration ,AC The code is as follows ：

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

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T; 
    cin>>T;
	while(T--)
	{
        int n;
        cin>>n;
        vector<int>a(n),b(n);
        for(int i=0;i<n;i++)cin>>a[i];
        for(int i=0;i<n;i++)cin>>b[i];
        if(n==1){
            cout<<0<<'\n';
            continue;
        }
        ll sum = accumulate(a.begin(),a.end(),0)+accumulate(b.begin(),b.end(),0);
        vector<ll>dp(sum+1);
        dp[0]=1;
        for(int i=0 ;i<n;i++){
            for(int j = sum ; j >= 0;j--){
                if(dp[j]){
                    dp[j+a[i]]=1;
                    dp[j+b[i]]=1;
                    dp[j]=0;
                }
            }
        }
        
        ll kase = 1e18;
        ll sum1=0;
        for(int i=0;i<=sum;i++){
            if(dp[i]==0)continue;
            if(abs(sum-i*2)<kase){
                sum1=i;
                kase = abs(sum-i*2);
            }
        }
        ll ans=0;
      //  cout<<sum1<<'\n';
        ans+=sum1*sum1+(sum-sum1)*(sum-sum1);
        for(int i =0 ;i<n;i++){
            ans+=(n-2)*a[i]*a[i];
            ans+=(n-2)*b[i]*b[i];
        }
        cout<<ans<<'\n';
        
	}
	return 0;
}
#include<bits/stdc++.h>
using namespace std;
#define ll long long

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T; 
    cin>>T;
	while(T--)
	{
        int n;
        cin>>n;
        vector<int>a(n),b(n);
        for(int i=0;i<n;i++)cin>>a[i];
        for(int i=0;i<n;i++)cin>>b[i];
        if(n==1){
            cout<<0<<'\n';
            continue;
        }
        ll sum = accumulate(a.begin(),a.end(),0)+accumulate(b.begin(),b.end(),0);
        vector<ll>dp(sum+1);
        dp[0]=1;
        for(int i=0 ;i<n;i++){
            for(int j = sum ; j >= 0;j--){
                if(dp[j]){
                    dp[j+a[i]]=1;
                    dp[j+b[i]]=1;
                    dp[j]=0;
                }
            }
        }
        
        ll kase = 1e18;
        ll sum1=0;
        for(int i=0;i<=sum;i++){
            if(dp[i]==0)continue;
            if(abs(sum-i*2)<kase){
                sum1=i;
                kase = abs(sum-i*2);
            }
        }
        ll ans=0;
      //  cout<<sum1<<'\n';
        ans+=sum1*sum1+(sum-sum1)*(sum-sum1);
        for(int i =0 ;i<n;i++){
            ans+=(n-2)*a[i]*a[i];
            ans+=(n-2)*b[i]*b[i];
        }
        cout<<ans<<'\n';
        
	}
	return 0;
}

---

Here's another one STL,

It can be used accumulate（） To directly solve the sum of an array .