結果
問題 | No.1045 直方体大学 |
ユーザー | monkukui2 |
提出日時 | 2020-05-01 22:05:22 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 196 ms / 2,000 ms |
コード長 | 2,785 bytes |
コンパイル時間 | 1,566 ms |
コンパイル使用メモリ | 97,424 KB |
実行使用メモリ | 28,032 KB |
最終ジャッジ日時 | 2023-08-26 13:44:31 |
合計ジャッジ時間 | 2,125 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,376 KB |
testcase_01 | AC | 1 ms
4,376 KB |
testcase_02 | AC | 2 ms
4,380 KB |
testcase_03 | AC | 2 ms
4,376 KB |
testcase_04 | AC | 1 ms
4,376 KB |
testcase_05 | AC | 2 ms
4,376 KB |
testcase_06 | AC | 2 ms
4,380 KB |
testcase_07 | AC | 2 ms
4,380 KB |
testcase_08 | AC | 25 ms
19,272 KB |
testcase_09 | AC | 22 ms
18,892 KB |
testcase_10 | AC | 17 ms
17,136 KB |
testcase_11 | AC | 21 ms
16,692 KB |
testcase_12 | AC | 34 ms
27,960 KB |
testcase_13 | AC | 53 ms
28,032 KB |
testcase_14 | AC | 27 ms
18,896 KB |
testcase_15 | AC | 44 ms
26,928 KB |
testcase_16 | AC | 49 ms
28,032 KB |
testcase_17 | AC | 2 ms
4,376 KB |
testcase_18 | AC | 196 ms
27,976 KB |
ソースコード
#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; }