結果
問題 | No.777 再帰的ケーキ |
ユーザー |
|
提出日時 | 2019-03-18 22:08:40 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 702 ms / 2,000 ms |
コード長 | 2,150 bytes |
コンパイル時間 | 1,594 ms |
コンパイル使用メモリ | 186,464 KB |
実行使用メモリ | 48,904 KB |
最終ジャッジ日時 | 2024-07-19 06:18:08 |
合計ジャッジ時間 | 7,317 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 33 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:86:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 86 | scanf("%d %d %lld",&a,&b,&c); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
ソースコード
#include "bits/stdc++.h"using namespace std;#pragma warning(disable:4996)#define Seg_Max_N (1<<18)using Value = long long int;const Value ini =0;struct segtree {int N;vector<Value>dat;segtree() {}segtree(int n) :dat(2 * Seg_Max_N) {N = 1;while (N < n) N *= 2;for (int i = 0; i < 2 * N - 1; i++) {dat[i] = ini;}}Value connect(const Value&l, const Value&r) {return max(l,r);}// update k th elementvoid update(int k, Value a) {k += N - 1;dat[k] = a;while (k > 0) {k = (k - 1) / 2;const Value al(dat[k * 2 + 1]);const Value ar(dat[k * 2 + 2]);dat[k] = connect(al, ar);}}// min [a, b)Value query(int a, int b) { return query(a, b, 0, 0, N); }Value query(int a, int b, int k, int l, int r) {if (r <= a or b <= l) return ini;if (a <= l and r <= b) return dat[k];const int m = (l + r) / 2;const Value al(query(a, b, k * 2 + 1, l, m));const Value ar(query(a, b, k * 2 + 2, m, r));return connect(al, ar);}};struct cake {int a;int b;long long int c;};bool operator<(const cake&l, const cake&r) {return l.a<r.a;}template<typename T> struct Compress {map<T, int>mp;map<int, T>revmp;Compress(vector<T>vs) {setmp(vs);}Compress() :mp(), revmp() {}void setmp(vector<T>vs) {sort(vs.begin(), vs.end());vs.erase(unique(vs.begin(), vs.end()), vs.end());for (int i = 0; i < static_cast<int>(vs.size()); ++i) {mp[vs[i]] = i;revmp[i] = vs[i];}}};int main() {int N;cin>>N;map<int,vector<cake>>mp;vector<int>bs{ 0 };for (int i = 0; i < N; ++i) {int a,b;long long int c;scanf("%d %d %lld",&a,&b,&c);bs.push_back(b);mp[a].push_back(cake{ a,b,c });}Compress<int> cb(bs);segtree seg(N+1);seg.update(0,0);for (auto m : mp) {vector<long long int>nums;for (auto c : m.second) {long long int num = seg.query(0, cb.mp[c.b]);nums.push_back(num);}int id = 0;for (auto c : m.second) {seg.update(cb.mp[c.b], max(seg.query(cb.mp[c.b], cb.mp[c.b] + 1), nums[id] + c.c));id++;}}long long int answer=seg.query(0,N+1);cout<<answer<<endl;return 0;}