結果
問題 | No.777 再帰的ケーキ |
ユーザー |
![]() |
提出日時 | 2019-02-23 16:57:54 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 546 ms / 2,000 ms |
コード長 | 1,824 bytes |
コンパイル時間 | 1,002 ms |
コンパイル使用メモリ | 94,964 KB |
実行使用メモリ | 23,868 KB |
最終ジャッジ日時 | 2024-11-30 13:31:25 |
合計ジャッジ時間 | 5,713 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 33 |
ソースコード
#include <iostream>#include <algorithm>#include <cstring>#include <sstream>#include <map>#include <queue>#include <set>#include <vector>#include <stack>#include <cstdio>#include <cmath>#define mk make_pair#define pb push_back#define printf printf_s#define scanf scanf_susing namespace std;typedef long long int ll;typedef pair<ll, ll> pos;const ll MOD = 1000000007, N = 200010, dx[4] = { -1,1,0,0 }, dy[4] = { 0,0,-1,1 }, MIN = -72340172838076673, MAX = 72340172838076673;ll mn(ll a, ll b) {if (a == -1)return b;if (b == -1)return a;return min(a, b);}ll gcd(ll v1, ll v2) {if (v1 == 0)return v2; if (v2 == 0)return v1; if (v2 > v1)return gcd(v2%v1, v1); return gcd(v1%v2, v2);}ll pw(ll v1, ll v2) {ll v3 = 1;while (v2 > 0) {if (v2 % 2)v3 = (v3*v1) % MOD;v1 = (v1*v1) % MOD;v2 /= 2;}return v3;}struct ab {ll a, b;bool operator<(const ab& right) const {return right.b*a - right.a*b < 0;}};pair<pos, ll> ck[N];ll n, bt[N], ans = 0;set<ll> st;map<ll, ll> mp;void ad(ll v1, ll v2) {while (v1 <= n) {bt[v1] = max(bt[v1], v2);v1 += v1 & -v1;}}ll mx(ll v1) {ll v2 = 0;while (v1 > 0) { v2 = max(v2, bt[v1]); v1 -= v1 & -v1; }return v2;}int main() {cin >> n;for (int i = 1; i <= n; i++) {cin >> ck[i].first.first >> ck[i].first.second >> ck[i].second;st.insert(ck[i].first.second);}sort(ck + 1, ck + n + 1);for (int i = 1; !st.empty(); i++) { mp[*st.begin()] = i; st.erase(st.begin()); }queue<pos> q;for (int i = 1; i <= n; i++) {if (ck[i].first.first != ck[i - 1].first.first) {while (!q.empty()) { ad(q.front().first, q.front().second); q.pop(); }}ll v1 = ck[i].second + mx(mp[ck[i].first.second] - 1);ans = max(ans, v1);q.push(mk(mp[ck[i].first.second], v1));}cout << ans << endl;return 0;}