結果
問題 | No.1045 直方体大学 |
ユーザー | Rubikun |
提出日時 | 2020-05-01 22:19:08 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 322 ms / 2,000 ms |
コード長 | 2,502 bytes |
コンパイル時間 | 1,660 ms |
コンパイル使用メモリ | 172,168 KB |
実行使用メモリ | 81,968 KB |
最終ジャッジ日時 | 2023-08-26 14:46:54 |
合計ジャッジ時間 | 5,921 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 306 ms
81,692 KB |
testcase_01 | AC | 293 ms
81,828 KB |
testcase_02 | AC | 239 ms
81,716 KB |
testcase_03 | AC | 237 ms
81,712 KB |
testcase_04 | AC | 238 ms
81,688 KB |
testcase_05 | AC | 132 ms
81,692 KB |
testcase_06 | AC | 130 ms
81,968 KB |
testcase_07 | AC | 129 ms
81,688 KB |
testcase_08 | AC | 79 ms
81,708 KB |
testcase_09 | AC | 75 ms
81,688 KB |
testcase_10 | AC | 73 ms
81,820 KB |
testcase_11 | AC | 75 ms
81,768 KB |
testcase_12 | AC | 82 ms
81,804 KB |
testcase_13 | AC | 102 ms
81,760 KB |
testcase_14 | AC | 80 ms
81,712 KB |
testcase_15 | AC | 94 ms
81,692 KB |
testcase_16 | AC | 98 ms
81,736 KB |
testcase_17 | AC | 187 ms
81,732 KB |
testcase_18 | AC | 322 ms
81,808 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; } template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; } #define all(x) (x).begin(),(x).end() #define fi first #define se second #define si(x) int(x.size()) const int mod=1000000007,MAX=100005,INF=1<<30; int dp[1<<17][17][3][3]; int main(){ std::ifstream in("text.txt"); std::cin.rdbuf(in.rdbuf()); cin.tie(0); ios::sync_with_stdio(false); int N;cin>>N; vector<vector<int>> S(17,vector<int>(3)); S[0][0]=INF; S[0][1]=INF; S[0][2]=INF; for(int i=0;i<N;i++){ for(int j=0;j<3;j++){ cin>>S[i+1][j]; } } for(int bit=0;bit<(1<<17);bit++){ for(int i=0;i<17;i++){ for(int j=0;j<3;j++){ for(int k=0;k<3;k++){ dp[bit][i][j][k]=-INF; dp[1][0][j][k]=0; } } } } for(int bit=0;bit<(1<<17);bit++){ for(int i=0;i<17;i++){ if(!(bit&(1<<i))) continue; for(int j=0;j<3;j++){ for(int k=j+1;k<3;k++){ if(dp[bit][i][j][k]<0) continue; for(int to=1;to<17;to++){ if(bit&(1<<to)) continue; for(int toj=0;toj<3;toj++){ for(int tok=toj+1;tok<3;tok++){ int a=S[i][j],b=S[i][k],c=S[i][(3-j-k)]; if(a>b) swap(a,b); int d=S[to][toj],e=S[to][tok],f=S[to][3-toj-tok]; if(d>e) swap(d,e); if(a>=d&&b>=e){ chmax(dp[bit|(1<<to)][to][toj][tok],dp[bit][i][j][k]+f); } } } } } } } } int ans=-INF; for(int bit=0;bit<(1<<17);bit++){ for(int i=0;i<17;i++){ for(int j=0;j<3;j++){ for(int k=0;k<3;k++){ chmax(ans,dp[bit][i][j][k]); } } } } cout<<ans<<endl; }