結果
問題 | No.497 入れ子の箱 |
ユーザー |
![]() |
提出日時 | 2022-01-02 01:38:05 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 18 ms / 5,000 ms |
コード長 | 1,699 bytes |
コンパイル時間 | 3,515 ms |
コンパイル使用メモリ | 143,864 KB |
実行使用メモリ | 11,264 KB |
最終ジャッジ日時 | 2024-10-10 21:01:15 |
合計ジャッジ時間 | 4,762 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 29 |
ソースコード
#include <cassert>#include <cmath>#include <algorithm>#include <iostream>#include <iomanip>#include <climits>#include <map>#include <queue>#include <set>#include <cstring>#include <vector>using namespace std;typedef long long ll;struct Box {int x;int y;int z;Box(int x = -1, int y = -1, int z = -1) {this->x = x;this->y = y;this->z = z;}bool operator<(const Box &n) const {return max(x, max(y, z)) > max(n.x, max(n.y, n.z));}};bool can_include(Box &b1, Box &b2) {if (b1.x > b2.x && b1.y > b2.y && b1.z > b2.z) return true;if (b1.x > b2.x && b1.y > b2.z && b1.z > b2.y) return true;if (b1.x > b2.y && b1.y > b2.x && b1.z > b2.z) return true;if (b1.x > b2.y && b1.y > b2.z && b1.z > b2.x) return true;if (b1.x > b2.z && b1.y > b2.y && b1.z > b2.x) return true;if (b1.x > b2.z && b1.y > b2.x && b1.z > b2.y) return true;return false;}int main() {int N;cin >> N;vector<Box> box_list;for (int i = 0; i < N; ++i) {Box box;cin >> box.x >> box.y >> box.z;box_list.push_back(box);}sort(box_list.begin(), box_list.end());ll dp[N + 1][N + 1];memset(dp, 0, sizeof(dp));ll ans = 1;for (int i = 1; i <= N; ++i) {Box &box = box_list[i - 1];dp[i][i] = 1;for (int j = 1; j < i; ++j) {dp[i][j] = dp[i - 1][j];Box &p_box = box_list[j - 1];if (not can_include(p_box, box)) continue;/*fprintf(stderr, "(%d, %d, %d) -> (%d, %d, %d)\n",p_box.x, p_box.y, p_box.z, box.x, box.y, box.z);*/dp[i][i] = max(dp[i][i], dp[i][j] + 1);ans = max(ans, dp[i][i]);}}cout << ans << endl;return 0;}