結果
問題 | No.497 入れ子の箱 |
ユーザー |
![]() |
提出日時 | 2017-03-27 21:45:09 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 14 ms / 5,000 ms |
コード長 | 1,182 bytes |
コンパイル時間 | 1,037 ms |
コンパイル使用メモリ | 93,428 KB |
実行使用メモリ | 8,576 KB |
最終ジャッジ日時 | 2024-07-06 09:46:33 |
合計ジャッジ時間 | 2,281 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 29 |
ソースコード
#include <algorithm>#include <cmath>#include <iostream>#include <map>#include <queue>#include <set>#include <string>#include <vector>#define rep(i, n) for (int i = 0; i < (n); i++)#define rrep(i, n) for (int i = (n)-1; i >= 0; i--)using namespace std;using lli = long long int;int n;vector<vector<int>> box;vector<int> len(3), e[100005];bool can(int i, int j){return box[i][0] > box[j][0]&& box[i][1] > box[j][1] && box[i][2] > box[j][2];}lli memo[100005];lli get(int cur, int par){if (memo[cur])return memo[cur];else {lli ans = 0;for (auto s : e[cur]) {if (s != par) {ans = max(ans, get(s, cur));}}return memo[cur] = ans + 1;}}int main(){cin >> n;rep(i, n){cin >> len[0] >> len[1] >> len[2];sort(len.begin(), len.end());box.push_back(len);}rep(i, n) rep(j, n){if (i == j)continue;if (can(i, j)) {e[i].push_back(j);}}lli ans = 0;rep(i, n){ans = max(get(i, -1), ans);}cout << ans << endl;}