Submission #1305874
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; if(i>0){ if(box[i-1][0]==box[i][0]&&dp[insertionPoint]==INF){//同じ幅で積み重ねないように continue; } } 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]; } } //O(nlog(n))
Submission Info
Submission Time | |
---|---|
Task | D - プレゼント |
User | inmir |
Language | Java8 (OpenJDK 1.8.0) |
Score | 30 |
Code Size | 1275 Byte |
Status | WA |
Exec Time | 642 ms |
Memory | 91916 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 | 94 ms | 18900 KB |
sample1.txt | AC | 94 ms | 21204 KB |
sample2.txt | AC | 94 ms | 21844 KB |
sample3.txt | AC | 94 ms | 19796 KB |
subtask0_0.txt | AC | 117 ms | 17748 KB |
subtask0_1.txt | AC | 101 ms | 21844 KB |
subtask0_10.txt | AC | 142 ms | 24620 KB |
subtask0_11.txt | AC | 142 ms | 23760 KB |
subtask0_12.txt | AC | 143 ms | 21204 KB |
subtask0_13.txt | AC | 153 ms | 23848 KB |
subtask0_14.txt | AC | 142 ms | 23912 KB |
subtask0_2.txt | AC | 104 ms | 19924 KB |
subtask0_3.txt | AC | 120 ms | 21844 KB |
subtask0_4.txt | AC | 142 ms | 23124 KB |
subtask0_5.txt | AC | 115 ms | 18768 KB |
subtask0_6.txt | AC | 148 ms | 25580 KB |
subtask0_7.txt | AC | 140 ms | 21844 KB |
subtask0_8.txt | AC | 130 ms | 22996 KB |
subtask0_9.txt | AC | 130 ms | 22356 KB |
subtask1_0.txt | AC | 528 ms | 63332 KB |
subtask1_1.txt | AC | 154 ms | 25964 KB |
subtask1_10.txt | AC | 563 ms | 81424 KB |
subtask1_11.txt | AC | 581 ms | 87764 KB |
subtask1_12.txt | AC | 612 ms | 82916 KB |
subtask1_13.txt | AC | 626 ms | 81724 KB |
subtask1_14.txt | WA | 622 ms | 91916 KB |
subtask1_2.txt | AC | 325 ms | 41488 KB |
subtask1_3.txt | AC | 614 ms | 64552 KB |
subtask1_4.txt | AC | 642 ms | 87624 KB |
subtask1_5.txt | WA | 295 ms | 40184 KB |
subtask1_6.txt | WA | 556 ms | 64244 KB |
subtask1_7.txt | WA | 452 ms | 60456 KB |
subtask1_8.txt | WA | 606 ms | 64648 KB |
subtask1_9.txt | WA | 474 ms | 62532 KB |