Submission #1305885
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){ 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 | 1338 Byte |
Status | WA |
Exec Time | 644 ms |
Memory | 88588 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 | 100 ms | 20820 KB |
sample1.txt | AC | 92 ms | 19796 KB |
sample2.txt | AC | 92 ms | 19796 KB |
sample3.txt | AC | 91 ms | 21844 KB |
subtask0_0.txt | AC | 129 ms | 21204 KB |
subtask0_1.txt | AC | 102 ms | 21840 KB |
subtask0_10.txt | AC | 137 ms | 25448 KB |
subtask0_11.txt | AC | 148 ms | 26068 KB |
subtask0_12.txt | AC | 141 ms | 24488 KB |
subtask0_13.txt | AC | 141 ms | 27268 KB |
subtask0_14.txt | AC | 142 ms | 23728 KB |
subtask0_2.txt | AC | 104 ms | 21844 KB |
subtask0_3.txt | AC | 118 ms | 22100 KB |
subtask0_4.txt | AC | 137 ms | 22504 KB |
subtask0_5.txt | AC | 114 ms | 20948 KB |
subtask0_6.txt | AC | 139 ms | 25444 KB |
subtask0_7.txt | AC | 142 ms | 25448 KB |
subtask0_8.txt | AC | 139 ms | 23252 KB |
subtask0_9.txt | AC | 128 ms | 20436 KB |
subtask1_0.txt | AC | 540 ms | 66748 KB |
subtask1_1.txt | AC | 156 ms | 25452 KB |
subtask1_10.txt | AC | 551 ms | 80716 KB |
subtask1_11.txt | AC | 577 ms | 85868 KB |
subtask1_12.txt | WA | 638 ms | 87552 KB |
subtask1_13.txt | WA | 644 ms | 88588 KB |
subtask1_14.txt | AC | 618 ms | 81468 KB |
subtask1_2.txt | AC | 316 ms | 40348 KB |
subtask1_3.txt | AC | 602 ms | 68380 KB |
subtask1_4.txt | AC | 637 ms | 85804 KB |
subtask1_5.txt | AC | 303 ms | 40724 KB |
subtask1_6.txt | AC | 567 ms | 65744 KB |
subtask1_7.txt | AC | 474 ms | 58988 KB |
subtask1_8.txt | WA | 606 ms | 63396 KB |
subtask1_9.txt | AC | 461 ms | 60920 KB |