Submission #923446
Source Code Expand
import java.util.ArrayList; import java.util.Arrays; import java.util.Scanner; import java.util.function.BiFunction; public class Main { Scanner sc = new Scanner(System.in); public static void main(String[] args) { new Main().run(); } class Box { int h, w; } class BIT<T> { int n; ArrayList<T> bit; BiFunction<T, T, T> bif; BIT(int n, BiFunction<T, T, T> bif, T defaultValue) { this.n = n; bit = new ArrayList<>(n + 1); for (int i = 0; i < n + 1; ++i) { bit.add(defaultValue); } this.bif = bif; } void update(int i, T v) { for (int x = i; x <= n; x += x & -x) { bit.set(x, bif.apply(bit.get(x), v)); } } T reduce(int i, T defaultValue) { T ret = defaultValue; for (int x = i; x > 0; x -= x & -x) { ret = bif.apply(ret, bit.get(x)); } return ret; } } void run() { int n = ni(); Box[] list = new Box[n]; for (int i = 0; i < n; ++i) { int w = ni(); int h = ni(); Box b = new Box(); b.w = w; b.h = h; list[i] = b; } Arrays.sort(list, (a, b) -> { if (a.h == b.h) { return b.w - a.w; } else { return a.h - b.h; } }); BIT<Integer> bit = new BIT<>(100000, Integer::max, 0); int[] dp = new int[n + 1]; for (int i = 1; i <= n; ++i) { dp[i] = bit.reduce(list[i - 1].w - 1, 0) + 1; bit.update(list[i - 1].w, dp[i]); } int max = 0; for (int i = 1; i <= n; ++i) { max = Math.max(max, dp[i]); } System.out.println(max); } int ni() { return Integer.parseInt(sc.next()); } void debug(Object... os) { System.err.println(Arrays.deepToString(os)); } }
Submission Info
Submission Time | |
---|---|
Task | D - プレゼント |
User | arukuka |
Language | Java8 (OpenJDK 1.8.0) |
Score | 100 |
Code Size | 1836 Byte |
Status | AC |
Exec Time | 880 ms |
Memory | 57020 KB |
Judge Result
Set Name | Sample | Subtask0 | All | ||||||
---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 30 / 30 | 70 / 70 | ||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Sample | sample0.txt, sample1.txt, sample2.txt, sample3.txt |
Subtask0 | subtask0_0.txt, subtask0_1.txt, subtask0_10.txt, subtask0_11.txt, subtask0_12.txt, subtask0_13.txt, subtask0_14.txt, subtask0_2.txt, subtask0_3.txt, subtask0_4.txt, subtask0_5.txt, subtask0_6.txt, subtask0_7.txt, subtask0_8.txt, subtask0_9.txt, sample0.txt, sample1.txt, sample2.txt, sample3.txt |
All | subtask0_0.txt, subtask0_1.txt, subtask0_10.txt, subtask0_11.txt, subtask0_12.txt, subtask0_13.txt, subtask0_14.txt, subtask0_2.txt, subtask0_3.txt, subtask0_4.txt, subtask0_5.txt, subtask0_6.txt, subtask0_7.txt, subtask0_8.txt, subtask0_9.txt, subtask1_0.txt, subtask1_1.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_2.txt, subtask1_3.txt, subtask1_4.txt, subtask1_5.txt, subtask1_6.txt, subtask1_7.txt, subtask1_8.txt, subtask1_9.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample0.txt | AC | 237 ms | 15436 KB |
sample1.txt | AC | 226 ms | 15180 KB |
sample2.txt | AC | 228 ms | 15676 KB |
sample3.txt | AC | 217 ms | 14928 KB |
subtask0_0.txt | AC | 275 ms | 16880 KB |
subtask0_1.txt | AC | 227 ms | 15172 KB |
subtask0_10.txt | AC | 282 ms | 17464 KB |
subtask0_11.txt | AC | 282 ms | 16940 KB |
subtask0_12.txt | AC | 291 ms | 19160 KB |
subtask0_13.txt | AC | 304 ms | 19064 KB |
subtask0_14.txt | AC | 285 ms | 17324 KB |
subtask0_2.txt | AC | 231 ms | 15180 KB |
subtask0_3.txt | AC | 240 ms | 15436 KB |
subtask0_4.txt | AC | 287 ms | 19120 KB |
subtask0_5.txt | AC | 230 ms | 15304 KB |
subtask0_6.txt | AC | 296 ms | 19132 KB |
subtask0_7.txt | AC | 287 ms | 17732 KB |
subtask0_8.txt | AC | 326 ms | 18592 KB |
subtask0_9.txt | AC | 261 ms | 18332 KB |
subtask1_0.txt | AC | 708 ms | 36156 KB |
subtask1_1.txt | AC | 284 ms | 18728 KB |
subtask1_10.txt | AC | 663 ms | 56776 KB |
subtask1_11.txt | AC | 705 ms | 39116 KB |
subtask1_12.txt | AC | 792 ms | 57020 KB |
subtask1_13.txt | AC | 880 ms | 56600 KB |
subtask1_14.txt | AC | 845 ms | 54648 KB |
subtask1_2.txt | AC | 499 ms | 32784 KB |
subtask1_3.txt | AC | 787 ms | 39020 KB |
subtask1_4.txt | AC | 744 ms | 47844 KB |
subtask1_5.txt | AC | 468 ms | 29428 KB |
subtask1_6.txt | AC | 671 ms | 39776 KB |
subtask1_7.txt | AC | 607 ms | 34452 KB |
subtask1_8.txt | AC | 652 ms | 40236 KB |
subtask1_9.txt | AC | 599 ms | 34228 KB |