結果
問題 | No.1045 直方体大学 |
ユーザー | Chanyuh |
提出日時 | 2020-05-02 17:47:58 |
言語 | C++11 (gcc 11.4.0) |
結果 |
MLE
|
実行時間 | - |
コード長 | 2,411 bytes |
コンパイル時間 | 1,366 ms |
コンパイル使用メモリ | 124,592 KB |
実行使用メモリ | 617,728 KB |
最終ジャッジ日時 | 2024-06-09 19:16:28 |
合計ジャッジ時間 | 9,692 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 1 ms
6,812 KB |
testcase_02 | AC | 2 ms
6,816 KB |
testcase_03 | AC | 2 ms
6,820 KB |
testcase_04 | AC | 1 ms
6,820 KB |
testcase_05 | AC | 9 ms
9,600 KB |
testcase_06 | AC | 9 ms
9,472 KB |
testcase_07 | AC | 10 ms
9,344 KB |
testcase_08 | MLE | - |
testcase_09 | MLE | - |
testcase_10 | MLE | - |
testcase_11 | MLE | - |
testcase_12 | MLE | - |
testcase_13 | MLE | - |
testcase_14 | MLE | - |
testcase_15 | MLE | - |
testcase_16 | MLE | - |
testcase_17 | AC | 3 ms
6,944 KB |
testcase_18 | MLE | - |
ソースコード
#include<iostream> #include<string> #include<cstdio> #include<vector> #include<cmath> #include<algorithm> #include<functional> #include<iomanip> #include<queue> #include<ciso646> #include<random> #include<map> #include<set> #include<complex> #include<bitset> #include<stack> #include<unordered_map> #include<utility> #include<tuple> using namespace std; typedef long long ll; typedef unsigned int ui; const ll mod = 1700000007; const ll INF = (ll)1000000007 * 1000000007; typedef pair<int, int> P; #define stop char nyaa;cin>>nyaa; #define rep(i,n) for(int i=0;i<n;i++) #define per(i,n) for(int i=n-1;i>=0;i--) #define Rep(i,sta,n) for(int i=sta;i<n;i++) #define Per(i,sta,n) for(int i=n-1;i>=sta;i--) #define rep1(i,n) for(int i=1;i<=n;i++) #define per1(i,n) for(int i=n;i>=1;i--) #define Rep1(i,sta,n) for(int i=sta;i<=n;i++) typedef long double ld; const ld eps = 1e-8; const ld pi = acos(-1.0); typedef pair<ll, ll> LP; typedef pair<P,P> PP; int dx[4]={1,-1,0,0}; int dy[4]={0,0,1,-1}; int n; set<int> se; map<int,int> zaatu; vector<PP> items; int dp[50][(1 << 16)][50]; void solve(){ cin >> n; rep(i,n){ int a,b,c;cin >> a >> b >> c;vector<int> p={a,b,c};sort(p.begin(),p.end()); se.insert(a);se.insert(b);se.insert(c); items.emplace_back(P(p[0],p[1]),P(p[2],i)); items.emplace_back(P(p[0],p[2]),P(p[1],i)); items.emplace_back(P(p[1],p[2]),P(p[0],i)); } int max_l=0;auto idx=se.begin(); while(idx!=se.end()){ zaatu[*idx]=max_l; idx++; max_l+=1; } sort(items.begin(),items.end()); int N=(1 << n); rep(i,3*n){ int d=zaatu[items[i].first.second],h=items[i].second.first,id=items[i].second.second; //cout << d << " " << h << " " << id << endl; rep(S,N){ rep(j,max_l){ dp[i+1][S][j]=max(dp[i+1][S][j],dp[i][S][j]); if(S & (1 << id)) continue; //cout << j << " " << d << " " << h << endl; if(j<=d){ dp[i+1][S|(1 << id)][d]=max(dp[i+1][S|(1 << id)][d],dp[i][S][j]+h); //cout << i+1 << " " << (S|(1 << id)) << " " << d << " " << dp[i+1][S|(1 << id)][d] << endl; } } } } int ans=0; rep(S,N){ rep(j,max_l){ //cout << bitset<2>(S) << " " << j << " " << dp[3*n][S][j] << endl; ans=max(ans,dp[3*n][S][j]); } } cout << ans << endl; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(50); solve(); }