提出 #13251673

---

ソースコード 拡げる

#include<iostream>
#include<cmath>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<iomanip>
#include<queue>

using namespace std;

typedef long long ll;

typedef std::pair<int, int> ipair;
bool lessPair(const ipair& l, const ipair& r){return l.second < r.second;}
bool morePair(const ipair& l, const ipair& r){return l.second > r.second;}

template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

const ll MOD = 1e9 + 7;
// const long long INF = 1LL<<60;
void add(long long &a, long long b) { a += b; if (a >= MOD) a -= MOD; }
void sub(long long &a, long long b) { a -= b; if (a < 0) a += MOD; }
void mul(long long &a, long long b) { a *= b; a %= MOD; }
ll llmin(ll a, ll b) { if (a < b) return a; else return b; }
ll llmax(ll a, ll b) { if (a < b) return b; else return a; }
ll llabs(ll a) { if (a >= 0) return a; else return - a; }
ll llmodpow(ll a, ll n) {
   if (n == 0) return 1;
   ll tmp = llmodpow(a, n / 2);
   mul(tmp, tmp);
   if (n & 1) mul(tmp, a);
   return tmp;
}

int main() {
   int N;
   cin >> N;
   ll A[N][N];
   memset(A, 0, sizeof(A));
  
   ll ans = 0;
   for (int i = 0; i < N - 1; i++) {
      for (int j = i + 1; j < N; j++) {
         cin >> A[i][j];
         ans += A[i][j];
      }
   }
   // cout << ans << endl;
   for (int mask = 0; mask < pow(3, N); mask++) {
      int tmp = mask;
      int team = -1;
      ll ans_tmp = 0; 
      vector<int> q0, q1, q2;
      for (int pos = 0; pos < N; pos++) {
         team = tmp % 3;
         if (team == 0) {
            q0.push_back(pos); 
         } else if (team == 1) {
            q1.push_back(pos); 
         } else {
            q2.push_back(pos); 
         }
         tmp /= 3;
      }
      int size;

      size = q0.size();
      sort(q0.begin(), q0.end());
      for (int i = 0; i < size; i++) {
         for (int j = i + 1; j < size; j++) {
            ans_tmp += A[q0[i]][q0[j]];
         }
      }
      // cout << "q0: " << size << " " << ans_tmp << endl;
      size = q1.size();
      sort(q1.begin(), q1.end());
      for (int i = 0; i < size; i++) {
         for (int j = i + 1; j < size; j++) {
            ans_tmp += A[q1[i]][q1[j]];
         }
      }
      // cout << "q1: " << size << " " << ans_tmp << endl;
      size = q2.size();
      sort(q2.begin(), q2.end());
      for (int i = 0; i < size; i++) {
         for (int j = i + 1; j < size; j++) {
            ans_tmp += A[q2[i]][q2[j]];
         }
      }
      // cout << "q2: " << size << " " << ans_tmp << endl;
      // cout << ans << " " << ans_tmp << endl;
      chmax(ans, ans_tmp);
   }
   cout << ans << endl;
   return 0;
}

提出情報

ジャッジ結果