Submission #1305860
Source Code Expand
import java.util.Arrays; import java.util.Comparator; import java.util.Scanner; public class Main { public static void main(String[] args) { // TODO 自動生成されたメソッド・スタブ Scanner scan = new Scanner(System.in); int N=scan.nextInt(); int[][] box = new int[N][2]; for(int i=0;i<N;i++){ box[i][0]=scan.nextInt(); box[i][1]=scan.nextInt(); } Arrays.sort(box,new ArraySort()); final int INF = 1000000000; int dp[] = new int[N+1];//dp[i] = 単調増加の部分列i を作るのに最小の最後尾の数 //次の数a[i]について、dp[j]<a[i]<dp[j+1]であればdp[j+1]=a[i] for(int i=0;i<N+1;i++){ dp[i]=INF; } for(int i=0;i<N;i++){ int result = Arrays.binarySearch(dp,box[i][1]); int insertionPoint = (result>=0) ? result : ~result; dp[insertionPoint] =box[i][1]; } for(int i=0;i<N;i++){ if(dp[i+1]==INF){ System.out.println(i+1); break; } } } } class ArraySort implements Comparator<int[]>{ public int compare(int[] num1,int[] num2){ return num1[0]-num2[0]; } }
Submission Info
Submission Time | |
---|---|
Task | D - プレゼント |
User | inmir |
Language | Java8 (OpenJDK 1.8.0) |
Score | 30 |
Code Size | 1118 Byte |
Status | WA |
Exec Time | 664 ms |
Memory | 88688 KB |
Judge Result
Set Name | Sample | Subtask0 | All | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 30 / 30 | 0 / 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 | sample0.txt, sample1.txt, sample2.txt, sample3.txt, 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 | 92 ms | 19412 KB |
sample1.txt | AC | 93 ms | 20820 KB |
sample2.txt | AC | 91 ms | 20688 KB |
sample3.txt | AC | 93 ms | 19924 KB |
subtask0_0.txt | AC | 126 ms | 20180 KB |
subtask0_1.txt | AC | 99 ms | 20688 KB |
subtask0_10.txt | AC | 142 ms | 24680 KB |
subtask0_11.txt | AC | 147 ms | 26008 KB |
subtask0_12.txt | AC | 141 ms | 25704 KB |
subtask0_13.txt | AC | 146 ms | 25316 KB |
subtask0_14.txt | AC | 140 ms | 23380 KB |
subtask0_2.txt | AC | 105 ms | 18772 KB |
subtask0_3.txt | AC | 125 ms | 20564 KB |
subtask0_4.txt | AC | 139 ms | 24164 KB |
subtask0_5.txt | AC | 104 ms | 19540 KB |
subtask0_6.txt | AC | 148 ms | 23984 KB |
subtask0_7.txt | AC | 138 ms | 20712 KB |
subtask0_8.txt | AC | 137 ms | 25300 KB |
subtask0_9.txt | AC | 137 ms | 20964 KB |
subtask1_0.txt | AC | 508 ms | 64744 KB |
subtask1_1.txt | AC | 154 ms | 22924 KB |
subtask1_10.txt | AC | 573 ms | 81308 KB |
subtask1_11.txt | AC | 563 ms | 82124 KB |
subtask1_12.txt | AC | 598 ms | 80220 KB |
subtask1_13.txt | WA | 664 ms | 87376 KB |
subtask1_14.txt | WA | 622 ms | 87888 KB |
subtask1_2.txt | AC | 305 ms | 42324 KB |
subtask1_3.txt | WA | 577 ms | 63972 KB |
subtask1_4.txt | AC | 642 ms | 88688 KB |
subtask1_5.txt | WA | 282 ms | 40592 KB |
subtask1_6.txt | AC | 582 ms | 65860 KB |
subtask1_7.txt | AC | 479 ms | 61044 KB |
subtask1_8.txt | AC | 606 ms | 68356 KB |
subtask1_9.txt | AC | 482 ms | 61176 KB |