結果

問題 No.165 四角で囲え！
ユーザー scachescache
提出日時 2015-05-27 11:50:15
言語 Java21
(openjdk 21)
結果
AC  
実行時間 595 ms / 5,000 ms
コード長 1,829 bytes
コンパイル時間 5,246 ms
コンパイル使用メモリ 80,792 KB
実行使用メモリ 45,304 KB
最終ジャッジ日時 2024-12-26 03:32:21
合計ジャッジ時間 14,250 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 450 ms
44,048 KB
testcase_01 AC 128 ms
40,888 KB
testcase_02 AC 114 ms
41,216 KB
testcase_03 AC 123 ms
41,288 KB
testcase_04 AC 114 ms
41,252 KB
testcase_05 AC 504 ms
43,996 KB
testcase_06 AC 258 ms
42,840 KB
testcase_07 AC 117 ms
41,384 KB
testcase_08 AC 113 ms
41,512 KB
testcase_09 AC 132 ms
41,152 KB
testcase_10 AC 129 ms
40,668 KB
testcase_11 AC 473 ms
44,316 KB
testcase_12 AC 572 ms
44,740 KB
testcase_13 AC 488 ms
45,304 KB
testcase_14 AC 494 ms
44,404 KB
testcase_15 AC 462 ms
45,200 KB
testcase_16 AC 538 ms
44,344 KB
testcase_17 AC 578 ms
45,248 KB
testcase_18 AC 595 ms
44,512 KB
testcase_19 AC 503 ms
45,140 KB
testcase_20 AC 506 ms
45,132 KB
testcase_21 AC 531 ms
45,108 KB
testcase_22 AC 552 ms
45,008 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 


import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;
import java.util.TreeSet;

public class Main0264 {

	public static void main(String[] args) {
		new Main0264();
	}

	public Main0264() {
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		int b = sc.nextInt();
		int[] x = new int[n];
		int[] y = new int[n];
		int[] p = new int[n];
		for(int i=0;i<n;i++){
			x[i] = sc.nextInt();
			y[i] = sc.nextInt();
			p[i] = sc.nextInt();
		}
		solve(n, b, x, y, p);
	}

	private void solve(int n, int b, int[] x, int[] y, int[] p) {
		int[] cx = compress(x);
		int[] cy = compress(y);

		int M = n+1;
		int[][] point = new int[M][M];
		int[][] count = new int[M][M];
		
		
		for(int i=0;i<n;i++){
			point[cy[i]+1][cx[i]+1] += p[i];
			count[cy[i]+1][cx[i]+1]++;
		}
		
		for(int i=0;i<M;i++){
			for(int j=1;j<M;j++){
				point[i][j] += point[i][j-1];
				count[i][j] += count[i][j-1];
			}
		}
		
		for(int i=1;i<M;i++){
			for(int j=0;j<M;j++){
				point[i][j] += point[i-1][j];
				count[i][j] += count[i-1][j];
			}
		}
		
		int res = 0;
		for(int i=1;i<M;i++){
			for(int j=1;j<M;j++){
				int ey = i;
				for(int k=M-1;k>=j;k--){
					while(ey<M){
						int cp = point[ey][k] + point[i-1][j-1] 
								- point[i-1][k] - point[ey][j-1];
						if(cp<=b){
							int cc = count[ey][k] + count[i-1][j-1] 
									- count[i-1][k] - count[ey][j-1];
							res = Math.max(res, cc);
							ey++;
						}else{
							break;
						}
					}
				}
			}
		}
				
		System.out.println(res);
	}
	
	private int[] compress(int[] x){
		TreeSet<Integer> set = new TreeSet<>();
		
		for(int v: x)
			set.add(v);
		
		Integer[] ia = new Integer[set.size()];
		set.toArray(ia);
		int[] cx = new int[x.length];
		for(int i=0;i<cx.length;i++)
			cx[i] = Arrays.binarySearch(ia, x[i]);
		
		return cx;
	}
}
0