結果

問題 No.1703 Much Matching
ユーザー ks2m
提出日時 2021-10-08 22:40:22
言語 Java
(openjdk 23)
結果
TLE  
実行時間 -
コード長 924 bytes
コンパイル時間 2,560 ms
コンパイル使用メモリ 84,548 KB
実行使用メモリ 120,320 KB
最終ジャッジ日時 2024-07-23 05:45:40
合計ジャッジ時間 39,402 ms
ジャッジサーバーID
(参考情報)
judge4 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 30 TLE * 4 -- * 1
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int q = sc.nextInt();
Obj[] arr = new Obj[q];
for (int i = 0; i < q; i++) {
Obj o = new Obj();
o.a = sc.nextInt();
o.b = sc.nextInt();
arr[i] = o;
}
sc.close();
Arrays.sort(arr, (o1, o2) -> {
if (o1.a != o2.a) {
return o1.a - o2.a;
}
return o2.b - o1.b;
});
int[] dp = new int[m + 1];
for (int i = 1; i <= m; i++) {
dp[i] = Integer.MAX_VALUE;
}
for (int i = 0; i < q; i++) {
int idx = Arrays.binarySearch(dp, arr[i].b);
if (idx < 0) idx = ~idx;
dp[idx] = arr[i].b;
}
int lis = Arrays.binarySearch(dp, Integer.MAX_VALUE - 1);
if (lis < 0) {
lis = ~lis;
lis--;
}
System.out.println(lis);
}
static class Obj {
int a, b;
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0