チームの分け方 \(N-1\) 通りそれぞれを時間計算量 \(O(N)\) かけて調べていては、全体の時間計算量が \(O(N^2)\) となり実行時間制限に間に合いません。

そこで、以下の手続きで全ての分け方を時間計算量 \(O(N)\) で調べます。

• 最初、 \(a=0,b=A_1+A_2+\dots+A_{N}\) 、暫定解 \(ans=\infty\) とする。
  • \(a\) はチーム A の実力値の合計、 \(b\) はチーム B の実力値の合計を表す。
• \(i=1,2,\dots,N-1\) について、以下を繰り返す。
  • \(a\) に \(A_i\) 加算、 \(b\) から \(A_i\) 減算する。
    • この時点で、 \(a\) はメンバー \(1,2,\dots,i\) の実力値の合計、 \(b\) はメンバー \(i+1,i+2,\dots,N\) の実力値の合計である。
  • \(ans\) を \(\min(ans,|a-b|)\) に更新する。

こうすることで、全ての分け方を時間計算量 \(O(N)\) で調べることができます。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

int main(){
  int N;
  cin >> N;
  vector<ll> A(N);
  ll a=0,b=0,res=8e18;
  for(auto &nx : A){
    cin >> nx;
    b+=nx;
  }
  for(ll i=0;i<N-1;i++){
    b-=A[i];
    a+=A[i];
    res=min(res,abs(a-b));
  }
  cout << res << "\n";
  return 0;
}