結果

問題 No.1045 直方体大学
コンテスト
ユーザー erbowl
提出日時 2020-05-06 09:49:52
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,525 bytes
コンパイル時間 2,241 ms
コンパイル使用メモリ 203,976 KB
最終ジャッジ日時 2025-01-10 07:10:14
ジャッジサーバーID
（参考情報） 		judge1 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 14 TLE * 3
権限があれば一括ダウンロードができます

ソースコード

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