結果

問題 No.1045 直方体大学
ユーザー erbowlerbowl
提出日時 2020-05-06 09:49:52
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 1,525 bytes
コンパイル時間 2,259 ms
コンパイル使用メモリ 211,592 KB
実行使用メモリ 13,756 KB
最終ジャッジ日時 2024-06-28 09:01:15
合計ジャッジ時間 6,288 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
13,756 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 2 ms
6,944 KB
testcase_05 AC 2 ms
6,944 KB
testcase_06 AC 2 ms
6,944 KB
testcase_07 AC 2 ms
6,940 KB
testcase_08 AC 24 ms
6,944 KB
testcase_09 AC 16 ms
6,948 KB
testcase_10 AC 19 ms
6,940 KB
testcase_11 AC 23 ms
6,944 KB
testcase_12 AC 199 ms
6,944 KB
testcase_13 TLE -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

typedef long long ll;
typedef long double ld;
#include <bits/stdc++.h>
using namespace std;


struct p {
    ll a,b,c;
};
int main() {
    ll n;
    std::cin >> n;
    vector<p> elm(n*6);
    vector<vector<ll>> edges(n*6);
    for (int i = 0; i < n; i++) {
        vector<ll> tmp(3);
        std::cin >> tmp[0]>>tmp[1]>>tmp[2];
        for (int j = 0; j < 6; j++) {
            elm[6*i+j].a = tmp[0];
            elm[6*i+j].b = tmp[1];
            elm[6*i+j].c = tmp[2];
            next_permutation(tmp.begin(),tmp.end());
        }
    }
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if(i==j)continue;
            for (int ii = 0; ii < 6; ii++) {
                for (int jj = 0; jj < 6; jj++) {
                    ll l = 6*i+ii;
                    ll r = 6*j+jj;
                    // l < r
                    if(elm[l].a<=elm[r].a&&elm[l].b<=elm[r].b){
                        edges[l].push_back(r);
                    }
                }
            }
        }
    }
    vector<bool> used(n,false);
    int ans = 0;
    function<void(int, int)> rec = [&] (int now, int height) {
        height += elm[now].c;
        ans = max(ans,height);
        for (auto e : edges[now]) {
            if(used[e/6])continue;
            used[e/6] = true;
            rec(e, height);
            used[e/6] = false;
        }
    };
    for (int i = 0; i < n*6; i++) {
        used[i/6] = true;
        rec(i,0);
        used[i/6] = false;
    }
    
    std::cout << ans << std::endl;
}
0