結果
問題 |
No.1045 直方体大学
|
ユーザー |
|
提出日時 | 2020-05-02 00:41:43 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 303 ms / 2,000 ms |
コード長 | 1,854 bytes |
コンパイル時間 | 1,918 ms |
コンパイル使用メモリ | 175,128 KB |
実行使用メモリ | 36,736 KB |
最終ジャッジ日時 | 2024-12-25 18:47:12 |
合計ジャッジ時間 | 3,848 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 17 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; constexpr char newl = '\n'; constexpr ll INF = 1e15; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int n; cin >> n; vector< vector<ll> > v(3, vector<ll>(n)); for (int i = 0; i < n; i++) { cin >> v[0][i] >> v[1][i] >> v[2][i]; } vector< vector< vector<ll> > > dp(3, vector< vector<ll> >(n, vector<ll>(1 << n, -INF))); for (int i = 0; i < n; i++) { dp[0][i][1 << i] = v[0][i]; dp[1][i][1 << i] = v[1][i]; dp[2][i][1 << i] = v[2][i]; } for (int i = 1; i < (1 << n) - 1; i++) { for (int j = 0; j < n; j++) { if (i >> j & 1) { for (int k = 0; k < n; k++) { if (i >> k & 1) continue; for (int l = 0; l < 3; l++) { if (dp[l][j][i] <= -INF) continue; ll minv_j = min(v[(l + 1) % 3][j], v[(l + 2) % 3][j]); ll maxv_j = max(v[(l + 1) % 3][j], v[(l + 2) % 3][j]); for (int m = 0; m < 3; m++) { ll minv_k = min(v[(m + 1) % 3][k], v[(m + 2) % 3][k]); ll maxv_k = max(v[(m + 1) % 3][k], v[(m + 2) % 3][k]); if (minv_k <= minv_j && maxv_k <= maxv_j) { dp[m][k][i | (1 << k)] = max(dp[m][k][i | (1 << k)], dp[l][j][i] + v[m][k]); } } } } } } } ll ans = -INF; for (int i = 0; i < 3; i++) { for (int j = 0; j < n; j++) { for (int k = 0; k < (1 << n); k++) { ans = max(ans, dp[i][j][k]); } } } cout << ans << newl; return 0; }