結果
問題 | No.777 再帰的ケーキ |
ユーザー |
|
提出日時 | 2018-12-29 13:37:07 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 291 ms / 2,000 ms |
コード長 | 2,051 bytes |
コンパイル時間 | 1,308 ms |
コンパイル使用メモリ | 128,612 KB |
実行使用メモリ | 27,512 KB |
最終ジャッジ日時 | 2024-06-13 02:26:00 |
合計ジャッジ時間 | 4,770 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 33 |
ソースコード
import std.stdio, std.string, std.conv;import std.range, std.algorithm, std.array, std.typecons, std.container;import std.math, std.numeric, core.bitop;alias Cake = Tuple!(int, "a", int, "b", int, "c");void main() {int n;scan(n);auto cs = new Cake[](n);foreach (i ; 0 .. n) {int a, b, c;scan(a, b, c);cs[i] = Cake(a, b, c);}int[int] zt;cs.sort!"a.b < b.b"();int rank = 1;zt[cs[0].b] = rank;foreach (i ; 1 .. n) {if (cs[i].b == cs[i-1].b) {continue;}rank++;zt[cs[i].b] = rank;}auto bit = FenwickTree!(long)(n + 10);cs.multiSort!("a.a < b.a", "a.b > b.b")();auto cur = new long[](n + 10);foreach (i ; 0 .. n) {auto res = bit.pmax(zt[cs[i].b]);res += cs[i].c;if (res > cur[zt[cs[i].b]]) {bit.update(zt[cs[i].b], res);cur[zt[cs[i].b]] = res;}}auto ans = bit.pmax(n + 10);writeln(ans);}struct FenwickTree(T) {private {int _size;T[] _data;}this(int N) {_size = N;_data = new T[](_size + 1);}void update(int i, T x) {i++;while (i <= _size) {_data[i] = max(_data[i], x);i += i & (-i);}}T pmax(int r) {T res = 0;while (r > 0) {res = max(res, _data[r]);r -= r & (-r);}return res;}}void scan(T...)(ref T args) {import std.stdio : readln;import std.algorithm : splitter;import std.conv : to;import std.range.primitives;auto line = readln().splitter();foreach (ref arg; args) {arg = line.front.to!(typeof(arg));line.popFront();}assert(line.empty);}void fillAll(R, T)(ref R arr, T value) {static if (is(typeof(arr[] = value))) {arr[] = value;}else {foreach (ref e; arr) {fillAll(e, value);}}}