結果
問題 | No.777 再帰的ケーキ |
ユーザー |
![]() |
提出日時 | 2020-12-16 18:53:41 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 1,557 ms / 2,000 ms |
コード長 | 2,436 bytes |
コンパイル時間 | 2,129 ms |
コンパイル使用メモリ | 79,512 KB |
実行使用メモリ | 83,072 KB |
最終ジャッジ日時 | 2024-09-20 05:15:02 |
合計ジャッジ時間 | 15,183 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 33 |
ソースコード
import java.util.*;import java.io.*;public class Main {public static void main (String[] args) throws Exception {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));int n = Integer.parseInt(br.readLine());Cake[] cakes = new Cake[n];for (int i = 0; i < n; i++) {cakes[i] = new Cake(br.readLine());}Arrays.sort(cakes);Cake.doCompress();int size = 1;long max = 0;BinaryIndexedTree bit = new BinaryIndexedTree(Cake.size);for (Cake c : cakes) {long next = bit.getMax(c.getIdx() - 1) + c.cal;max = Math.max(max, next);bit.set(c.getIdx(), next);}System.out.println(max);}static class Cake implements Comparable<Cake> {static int size = 1;static TreeMap<Integer, Integer> compress = new TreeMap<>();static void doCompress() {for (int x : compress.keySet()) {compress.put(x, size);size++;}}int width;int height;int cal;public Cake(int width, int height, int cal) {this.width = width;this.height = height;this.cal = cal;compress.put(height, 0);}public Cake(String line) {this(line.split(" ", 3));}public Cake(String[] element) {this(Integer.parseInt(element[0]), Integer.parseInt(element[1]), Integer.parseInt(element[2]));}public int getIdx() {return compress.get(height);}public int compareTo(Cake another) {if (width == another.width) {return another.height - height;} else {return width - another.width;}}}}class BinaryIndexedTree {int size;long[] tree;public BinaryIndexedTree(int size) {this.size = size;tree = new long[size];}public void set(int idx, long value) {int mask = 1;while (idx < size) {if ((idx & mask) != 0) {tree[idx] = Math.max(tree[idx], value);idx += mask;}mask <<= 1;}}public long getMax(int x) {int mask = 1;long ans = 0;while (x > 0) {if ((x & mask) != 0) {ans = Math.max(ans, tree[x]);x -= mask;}mask <<= 1;}return ans;}}