結果
問題 | No.777 再帰的ケーキ |
ユーザー |
![]() |
提出日時 | 2018-09-20 22:25:44 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 325 ms / 2,000 ms |
コード長 | 2,614 bytes |
コンパイル時間 | 2,371 ms |
コンパイル使用メモリ | 189,072 KB |
実行使用メモリ | 20,352 KB |
最終ジャッジ日時 | 2024-11-19 05:21:46 |
合計ジャッジ時間 | 5,559 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 33 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define pb push_back#define mp make_pair#define all(x) (x).begin(),(x).end()#define rep(i,n) for(int i=0;i<(n);i++)constexpr int MOD = 1000000007;typedef long long ll;typedef unsigned long long ull;typedef pair<int,int> pii;constexpr int dx[] = {1, 0, -1, 0, 1, 1, -1, -1};constexpr int dy[] = {0, -1, 0, 1, 1, -1, -1, 1};template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){os << "["; for (const auto &v : vec) {os << v << ","; } os << "]";return os; }template <typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &p){os << "(" << p.first << ", " << p.second << ")"; return os;}struct Phone {int h, w, t;bool operator<(const Phone &rhs) const {if (h == rhs.h) {return w > rhs.w;}return h < rhs.h;}};struct BIT {vector<ll> data;BIT(int n): data(n + 1) {}ll getmax(int a) {ll ret = 0;for(int i = a; i > 0; i -= i & -i) {ret = max(ret, data[i]);}return ret;}void update(int a, ll w) {for(int i = a; i < data.size(); i += i & -i) {data[i] = max(data[i], w);}}};// BIT解(想定解)ll solve1(int N, vector<Phone> &P) {sort(all(P));vector<int> W(N);for (int i = 0; i < N; i++) {W[i] = P[i].w;}sort(all(W));W.erase(unique(W.begin(), W.end()), W.end());BIT bit(N + 2);for(int i = 0; i < N; i++) {int k = lower_bound(all(W), P[i].w) - W.begin() - 1;k += 2; // for BITll mi = bit.getmax(k);bit.update(k + 1, mi + P[i].t);}return bit.getmax(N + 2);}// Naive DP解(O(N^2), TLE)ll solve2(int N, vector<Phone> &P) {sort(all(P));vector<ll> dp(N, 0);for(int i = 0; i < N; i++) {ll ma = 0;for(int j = 0; j < i; j++) {if (P[j].w >= P[i].w) continue;ma = max(ma, dp[j]);}dp[i] = ma + P[i].t;}return *max_element(all(dp));}void solve() {int N;cin >> N;map<pii, int> M;for(int i = 0; i < N; i++) {int h, w, t;cin >> h >> w >> t;M[{h, w}] = max(M[{h, w}], t);}vector<Phone> P;for(auto &&x : M) {P.push_back({x.first.first, x.first.second, x.second});}N = P.size();if (N > 2000) {cout << solve1(N, P) << endl;} else {ll ans1 = solve1(N, P);ll ans2 = solve2(N, P);if (ans1 != ans2) {cout << "Error: " << ans1 << " : " << ans2 << endl;} else {cout << ans1 << endl;}}}int main() {std::cin.tie(0);std::ios::sync_with_stdio(false);cout.setf(ios::fixed);cout.precision(16);solve();return 0;}