結果

問題 No.165 四角で囲え！
ユーザー uafr_csuafr_cs
提出日時 2017-11-09 13:28:38
言語 Java21
(openjdk 21)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 2,838 bytes
コンパイル時間 2,421 ms
コンパイル使用メモリ 78,848 KB
実行使用メモリ 60,872 KB
最終ジャッジ日時 2024-06-07 19:15:00
合計ジャッジ時間 20,952 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 AC 135 ms
54,156 KB
testcase_02 AC 138 ms
54,080 KB
testcase_03 AC 137 ms
54,260 KB
testcase_04 AC 143 ms
54,084 KB
testcase_05 AC 876 ms
57,584 KB
testcase_06 AC 338 ms
57,264 KB
testcase_07 AC 138 ms
54,060 KB
testcase_08 AC 135 ms
54,120 KB
testcase_09 AC 135 ms
54,116 KB
testcase_10 AC 136 ms
54,088 KB
testcase_11 AC 854 ms
57,352 KB
testcase_12 AC 944 ms
60,600 KB
testcase_13 AC 935 ms
60,092 KB
testcase_14 AC 1,125 ms
60,320 KB
testcase_15 AC 1,360 ms
60,636 KB
testcase_16 AC 1,140 ms
60,440 KB
testcase_17 AC 1,257 ms
60,324 KB
testcase_18 AC 862 ms
60,184 KB
testcase_19 AC 1,288 ms
59,660 KB
testcase_20 AC 1,255 ms
60,872 KB
testcase_21 AC 1,215 ms
60,044 KB
testcase_22 AC 1,326 ms
60,872 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Scanner;

public class Main {
	
	public static long get_sum(int lx, int ly, int rx, int ry, long[][] sums){
		final long ll = (lx == 0 || ly == 0) ? 0 : sums[ly - 1][lx - 1];
		final long lr = ly == 0 ? 0 : sums[ly - 1][rx];
		final long rl = lx == 0 ? 0 : sums[ry][lx - 1];
		final long rr = sums[ry][rx];
		
		return rr - rl - lr + ll;
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		final int N = sc.nextInt();
		final long B = sc.nextLong();
		
		long[] xs = new long[N];
		long[] ys = new long[N];
		long[] ps = new long[N];
		for(int i = 0; i < N; i++){
			xs[i] = sc.nextLong();
			ys[i] = sc.nextLong();
			ps[i] = sc.nextLong();
		}
		
		long[] sorted_x = xs.clone();
		long[] sorted_y = ys.clone();
		Arrays.sort(sorted_x); Arrays.sort(sorted_y);
		
		HashMap<Long, Integer> x_to_index = new HashMap<Long, Integer>();
		HashMap<Long, Integer> y_to_index = new HashMap<Long, Integer>();
		for(int i = 0; i < N; i++){
			x_to_index.put(sorted_x[i], i);
			y_to_index.put(sorted_y[i], i);
		}
		
		long[][] sorted_sum = new long[N][N];
		long[][] sorted_cnt = new long[N][N];
		for(int i = 0; i < N; i++){
			final int x_index = x_to_index.get(xs[i]);
			final int y_index = y_to_index.get(ys[i]);
			
			sorted_sum[y_index][x_index] = ps[i];
			sorted_cnt[y_index][x_index]++;
		}
		for(int y = 0; y < N; y++){
			for(int x = 0; x < N; x++){
				if(x != 0 && y != 0){
					sorted_sum[y][x] += sorted_sum[y - 1][x] + sorted_sum[y][x - 1] - sorted_sum[y - 1][x - 1];
					sorted_cnt[y][x] += sorted_cnt[y - 1][x] + sorted_cnt[y][x - 1] - sorted_cnt[y - 1][x - 1];
				}else if(x != 0){
					sorted_sum[y][x] += sorted_sum[y][x - 1];
					sorted_cnt[y][x] += sorted_cnt[y][x - 1];
				}else if(y != 0){ 
					sorted_sum[y][x] += sorted_sum[y - 1][x];
					sorted_cnt[y][x] += sorted_cnt[y - 1][x];
				}
			}
		}
		
		//System.out.println(Arrays.deepToString(sorted_sum));
		//System.out.println(Arrays.deepToString(sorted_cnt));
		
		long answer = 0;
			
		for(int x_upper = 0; x_upper < N; x_upper++){
			for(int x_lower = 0; x_lower <= x_upper; x_lower++){
				
				int y_upper = 0;
				for(int y_lower = 0; y_lower < N; y_lower++){
					//System.out.printf("(%d, %d) : (%d, %d)\n", x_lower, y_lower, x_upper, y_upper);
					
					final long cnt = get_sum(x_lower, y_lower, x_upper, y_upper, sorted_cnt);
					final long value = get_sum(x_lower, y_lower, x_upper, y_upper, sorted_sum);
					
					//System.out.println(value);
					if(cnt > 0 && value <= B){
						//System.out.println(cnt);
						answer = Math.max(answer, cnt);
						if(y_upper < N - 1){ y_upper++; y_lower--;}
					}else{
						if(y_upper < N - 1){ y_upper++; }
					}
				}
			}
		}
		
		System.out.println(answer);
	}
}
0