結果

問題 No.777 再帰的ケーキ
ユーザー tenten
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

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;
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0