結果
問題 | No.1045 直方体大学 |
ユーザー |
|
提出日時 | 2020-05-06 22:58:52 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 909 ms / 2,000 ms |
コード長 | 1,691 bytes |
コンパイル時間 | 2,374 ms |
コンパイル使用メモリ | 201,348 KB |
最終ジャッジ日時 | 2025-01-10 07:20:20 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 17 |
ソースコード
typedef long long ll; typedef long double ld; #include <bits/stdc++.h> using namespace std; int main() { ll n; std::cin >> n; vector<vector<ll>> abc(n,vector<ll>(3,0)); for (int i = 0; i < n; i++) { std::cin >> abc[i][0]>>abc[i][1]>>abc[i][2]; } vector<vector<vector<ll>>> dp((1<<18),vector<vector<ll>>(20,vector<ll>(3,0))); ll ans = 0; // 0 0が高さ for (int i = 1; i <= (1<<n); i++) { for (int j = 0; j < n; j++) { if(!(i & (1<<j)))continue; if(__builtin_popcount(i)==1){ dp[i][j][0] = abc[j][0]; dp[i][j][1] = abc[j][1]; dp[i][j][2] = abc[j][2]; ans = max({ ans, abc[j][0], abc[j][1], abc[j][2] }); continue; } for (int k = 0; k < n; k++) { if(!(i & (1<<k)))continue; if(j==k)continue; auto &d = dp[i][j]; auto &pd= dp[i&~(1<<j)][k]; for (int ii = 0; ii < 3; ii++) { for (int jj = 0; jj < 3; jj++) { if((abc[j][(ii+1)%3]<=abc[k][(jj+1)%3]&&abc[j][(ii+2)%3]<=abc[k][(jj+2)%3]) ||(abc[j][(ii+1)%3]<=abc[k][(jj+2)%3]&&abc[j][(ii+2)%3]<=abc[k][(jj+1)%3])){ d[ii] = max(d[ii],pd[jj]+abc[j][ii]); ans = max(ans,d[ii]); } } } } } } std::cout << ans << std::endl; }