Submission #1305911
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 を作るのに最小の最後尾の数 int dpw[] = new int[N+1]; //次の数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; dpw[i]=INF; } for(int i=0;i<N;i++){//同じ幅について、大きい方からチェックしたい int result = Arrays.binarySearch(dp,box[i][1]); int insertionPoint = (result>=0) ? result : ~result; /* if(insertionPoint>0&&dpw[insertionPoint-1]==box[i][0]){//同じ幅で積み重ねないように continue; }*/ dp[insertionPoint] =box[i][1]; dpw[insertionPoint] =box[i][0]; } 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){ if(num1[0]==num2[0]){ //幅が同じときは、高さが大きい方を先にする return num2[1]-num1[1]; } return num1[0]-num2[0]; } } //O(nlog(n))
Submission Info
Submission Time | |
---|---|
Task | D - プレゼント |
User | inmir |
Language | Java8 (OpenJDK 1.8.0) |
Score | 100 |
Code Size | 1537 Byte |
Status | AC |
Exec Time | 663 ms |
Memory | 87780 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 | 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 | 93 ms | 21716 KB |
sample1.txt | AC | 92 ms | 19796 KB |
sample2.txt | AC | 94 ms | 17748 KB |
sample3.txt | AC | 94 ms | 21460 KB |
subtask0_0.txt | AC | 130 ms | 19668 KB |
subtask0_1.txt | AC | 99 ms | 20820 KB |
subtask0_10.txt | AC | 143 ms | 25812 KB |
subtask0_11.txt | AC | 133 ms | 26412 KB |
subtask0_12.txt | AC | 144 ms | 25448 KB |
subtask0_13.txt | AC | 143 ms | 23656 KB |
subtask0_14.txt | AC | 143 ms | 21940 KB |
subtask0_2.txt | AC | 104 ms | 21972 KB |
subtask0_3.txt | AC | 116 ms | 22356 KB |
subtask0_4.txt | AC | 143 ms | 22356 KB |
subtask0_5.txt | AC | 105 ms | 21844 KB |
subtask0_6.txt | AC | 138 ms | 22868 KB |
subtask0_7.txt | AC | 142 ms | 24880 KB |
subtask0_8.txt | AC | 133 ms | 25776 KB |
subtask0_9.txt | AC | 128 ms | 20436 KB |
subtask1_0.txt | AC | 528 ms | 58440 KB |
subtask1_1.txt | AC | 152 ms | 22920 KB |
subtask1_10.txt | AC | 565 ms | 87780 KB |
subtask1_11.txt | AC | 561 ms | 82788 KB |
subtask1_12.txt | AC | 625 ms | 81500 KB |
subtask1_13.txt | AC | 663 ms | 80784 KB |
subtask1_14.txt | AC | 652 ms | 82204 KB |
subtask1_2.txt | AC | 335 ms | 40224 KB |
subtask1_3.txt | AC | 612 ms | 62476 KB |
subtask1_4.txt | AC | 627 ms | 82036 KB |
subtask1_5.txt | AC | 295 ms | 38736 KB |
subtask1_6.txt | AC | 565 ms | 65244 KB |
subtask1_7.txt | AC | 448 ms | 56108 KB |
subtask1_8.txt | AC | 590 ms | 63452 KB |
subtask1_9.txt | AC | 474 ms | 58144 KB |