結果

問題 No.1045 直方体大学
ユーザー monkukui2monkukui2
提出日時 2020-05-01 22:05:22
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 247 ms / 2,000 ms
コード長 2,785 bytes
コンパイル時間 936 ms
コンパイル使用メモリ 98,284 KB
実行使用メモリ 28,032 KB
最終ジャッジ日時 2024-12-25 10:47:58
合計ジャッジ時間 2,255 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <functional>
#include <bitset>

using namespace std;
using lint = long long int;
long long int INF = 1001001001001001LL;
int inf = 1000000007;
long long int MOD = 1000000007LL;
double PI = 3.1415926535897932;

template<typename T1,typename T2>inline void chmin(T1 &a,const T2 &b){if(a>b) a=b;}
template<typename T1,typename T2>inline void chmax(T1 &a,const T2 &b){if(a<b) a=b;}

#define ALL(a) a.begin(),a.end()
#define RALL(a) a.rbegin(),a.rend()

/* do your best */

lint dp[(1 << 16) + 1][16][3] = {};

int main() {
  
  // dp[bit][最後に積んだ id][向き]
  // (a, b)
  // (b, c)
  // (a, c)
  
  int n; cin >> n;
  vector<lint> a(n);
  vector<lint> b(n);
  vector<lint> c(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i] >> b[i] >> c[i];
  }


  // 最初は何積んでもいいで
  for (int i = 0; i < n; i++) {
    dp[(1 << i)][i][0] = c[i];
    dp[(1 << i)][i][1] = a[i];
    dp[(1 << i)][i][2] = b[i];
  }

  lint ans = 0;

  for (int bit = 0; bit < (1 << n); bit++) {
    for (int i = 0; i < n; i++) {
      for (int k = 0; k < 3; k++) {
        ans = max(ans, dp[bit][i][k]);
        if (dp[bit][i][k] == 0) continue;

        // まだ積んでないやつを試す
        for (int ni = 0; ni < n; ni++) {
          if (bit & (1 << ni)) continue;
          int yoko;
          int tate;
          if (k == 0) {
            yoko = a[i];
            tate = b[i];
          } else if (k == 1) {
            yoko = b[i];
            tate = c[i];
          } else {
            yoko = a[i];
            tate = c[i];
          }

          if (yoko > tate) swap(yoko, tate);
          
          // 三通り試す
          for (int nk = 0; nk < 3; nk++) {
            int nyoko;
            int ntate;
            lint add;
            if (nk == 0) {
              nyoko = a[ni];
              ntate = b[ni];
              add = c[ni];
            } else if (nk == 1) {
              nyoko = b[ni];
              ntate = c[ni];
              add = a[ni];
            } else {
              nyoko = a[ni];
              ntate = c[ni];
              add = b[ni];
            }

            if (nyoko > ntate) swap(nyoko, ntate);

            if (nyoko <= yoko and ntate <= tate) {
              lint nxtBit = bit | (1 << ni);
              dp[nxtBit][ni][nk] = max(dp[nxtBit][ni][nk], dp[bit][i][k] + add);
            }
          }
        }
      }
    }
  }

  cout << ans << endl;

  return 0;
}
0