結果
問題 | No.497 入れ子の箱 |
ユーザー |
![]() |
提出日時 | 2017-03-17 03:19:16 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 24 ms / 5,000 ms |
コード長 | 1,915 bytes |
コンパイル時間 | 1,050 ms |
コンパイル使用メモリ | 89,084 KB |
実行使用メモリ | 8,320 KB |
最終ジャッジ日時 | 2024-07-06 01:27:35 |
合計ジャッジ時間 | 2,149 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 29 |
ソースコード
#include <iostream> #include <assert.h> #include <tuple> #include <vector> #include <algorithm> using namespace std; typedef tuple<int,int,int> T; typedef vector<vector<int>> Graph; class Topological_Sort{ Graph G; public:vector<int> order; vector<bool> visited; void dfs(int v){ if(visited[v]) return; visited[v]=true; for(auto &to:G[v]){ dfs(to); } order.push_back(v); return; }; Topological_Sort(Graph &g) : G(g) { visited = vector<bool>(G.size()); for(int i=0;i<G.size();i++) dfs(i); reverse(order.begin(), order.end()); }; }; bool putin(T &A, T &B){//AがBに入るか int Ax,Ay,Az,Bx,By,Bz; tie(Ax,Ay,Az)=A; tie(Bx,By,Bz)=B; if(Ax<Bx&&Ay<By&&Az<Bz) return true; if(Ax<Bx&&Ay<Bz&&Az<By) return true; if(Ax<By&&Ay<Bx&&Az<Bz) return true; if(Ax<By&&Ay<Bz&&Az<Bx) return true; if(Ax<Bz&&Ay<Bx&&Az<By) return true; if(Ax<Bz&&Ay<By&&Az<Bx) return true; return false; } int main(){ int N; cin>>N; assert(1<=N&&N<=1000); vector<T> B; for(int i=0;i<N;i++){ int X,Y,Z; cin>>X>>Y>>Z; assert(1<=X&&X<100000000); assert(1<=Y&&Y<100000000); assert(1<=Z&&Z<100000000); B.emplace_back(X,Y,Z); } Graph G(N); for(int i=0;i<N;i++){ for(int j=0;j<N;j++){ if(putin(B[i],B[j])) G[i].push_back(j); } } Topological_Sort TS(G); vector<T> B2; for(auto o:TS.order) B2.push_back(B[o]); int DP[N]; fill(DP,DP+N,0); for(int i=N-1;i>=0;i--){ int maximum = 0; for(int j=i+1;j<N;j++){ if(putin(B2[i],B2[j])){ maximum=max(maximum,DP[j]); } } DP[i]=maximum+1; } int ans = 0; for(int i=0;i<N;i++){ ans=max(ans,DP[i]); } cout<<ans<<endl; return 0; }