結果
問題 | No.1045 直方体大学 |
ユーザー |
|
提出日時 | 2021-06-13 20:21:00 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,057 bytes |
コンパイル時間 | 2,222 ms |
コンパイル使用メモリ | 207,680 KB |
最終ジャッジ日時 | 2025-01-22 08:00:26 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 7 TLE * 9 MLE * 1 |
ソースコード
#include <bits/stdc++.h>using namespace std;int dp[1 << 16][50][50];set <int> S;map <int, int> memo;int N;int A[16];int B[16];int C[16];int main(void){cin.tie(0);ios::sync_with_stdio(false);cin >> N;for (int i = 0; i < N; i++){cin >> A[i] >> B[i] >> C[i];S.insert(A[i]);S.insert(B[i]);S.insert(C[i]);}int num = 0;for (auto it : S){memo[it] = num++;}for (int i = 0; i < N; i++){int a = memo[A[i]];int b = memo[B[i]];int c = memo[C[i]];dp[(1 << i)][a][b] = max(dp[(1 << i)][a][b], C[i]);dp[(1 << i)][b][a] = max(dp[(1 << i)][b][a], C[i]);dp[(1 << i)][a][c] = max(dp[(1 << i)][a][c], B[i]);dp[(1 << i)][c][a] = max(dp[(1 << i)][c][a], B[i]);dp[(1 << i)][b][c] = max(dp[(1 << i)][b][c], A[i]);dp[(1 << i)][c][b] = max(dp[(1 << i)][c][b], A[i]);}for (int i = 1; i < (1 << N); i++){for (int j = 0; j < num; j++){for (int k = 0; k < num; k++){for (int x = 0; x < N; x++){if ((i & (1 << x)) == 0){int bitmask = i + (1 << x);int a = memo[A[x]];int b = memo[B[x]];int c = memo[C[x]];if (a <= j && b <= k){dp[bitmask][a][b] = max(dp[bitmask][a][b], dp[i][j][k] + C[x]);}if (a <= k && b <= j){dp[bitmask][b][a] = max(dp[bitmask][b][a], dp[i][j][k] + C[x]);}if (b <= j && c <= k){dp[bitmask][b][c] = max(dp[bitmask][b][c], dp[i][j][k] + A[x]);}if (b <= k && c <= j){dp[bitmask][c][b] = max(dp[bitmask][c][b], dp[i][j][k] + A[x]);}if (a <= j && c <= k){dp[bitmask][a][c] = max(dp[bitmask][a][c], dp[i][j][k] + B[x]);}if (a <= k && c <= j){dp[bitmask][c][a] = max(dp[bitmask][c][a], dp[i][j][k] + B[x]);}}}}}}int res = 0;for (int i = 0; i < (1 << N); i++){for (int j = 0; j < num; j++){for (int k = 0; k < num; k++){res = max(res, dp[i][j][k]);}}}cout << res << '\n';return 0;}