結果

問題 No.1045 直方体大学
コンテスト
ユーザー saxofone111
提出日時 2021-03-09 12:12:21
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 272 ms / 2,000 ms
コード長 1,909 bytes
コンパイル時間 2,310 ms
コンパイル使用メモリ 201,384 KB
最終ジャッジ日時 2025-01-19 13:03:26
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"

#define MOD 1000000007
#define rep(i, n) for(ll i=0; i < (n); i++)
#define rrep(i, n) for(ll i=(n)-1; i >=0; i--)
#define ALL(v) v.begin(),v.end()
#define rALL(v) v.rbegin(),v.rend()
#define FOR(i, j, k) for(ll i=j;i<k;i++)
#define debug_print(var) cerr << #var << "=" << var <<endl;
#define DUMP(i, v)for(ll i=0;i<v.size();i++)cerr<<v[i]<<" "
#define fi first
#define se second

using namespace std;
typedef long long int ll;
typedef vector<ll> llvec;
typedef vector<double> dvec;
typedef pair<ll, ll> P;
typedef long double ld;
struct edge{ll x, c;};

struct block{
  ll a, b, c;
  P get(ll i){
    if(i==0)return {min(b, c), max(b, c)};
    else if(i==1)return {min(a, c), max(a, c)};
    else return {min(a, b), max(a, b)};
  }

  ll height(ll i){
    if(i==0)return a;
    else if(i==1)return b;
    else return c;
  }
  
};

/**************************************
** A main function starts from here  **
***************************************/
int main(){
  ll N;
  cin >> N;
  vector<block> v(N);
  rep(i, N){
    cin >> v[i].a >> v[i].b >> v[i].c;
  }
  vector<llvec> m(N*3);
  rep(k, N*3){
    ll i = k/3;
    ll j = k%3;
    auto [a, b] = v[i].get(j);
    rep(l, N*3){
      ll L = l/3;
      ll J = l%3;
      if(i==L)continue;
      auto [A, B] = v[L].get(J);
      if(A<=a and B<=b)m[k].push_back(l);
    }
  }

  vector<llvec> dp(1<<N, llvec(3*N, -1e18));
  ll ans = 0;
  rep(i, N){
    rep(k, 3){
      dp[1<<i][3*i+k] = v[i].height(k);
      ans = max(ans, v[i].height(k));
    }
  }
  rep(i, 1<<N){
    rep(k, 3*N){
      if(dp[i][k]==-1e18)continue;
      for(auto iv: m[k]){
        ll ind = iv/3;
        if((i>>ind)&1){
          continue;
        }else{
          dp[i | (1<<ind)][iv] = max(dp[i | (1<<ind)][iv], dp[i][k] + v[ind].height(iv%3));
          ans = max(ans, dp[i | (1<<ind)][iv]);
        }
      }
    }
  }
  cout << ans << endl;
  return 0;
}
0