結果

問題 No.165 四角で囲え！
ユーザー uafr_csuafr_cs
提出日時 2017-11-09 13:28:38
言語 Java21
(openjdk 21)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 2,838 bytes
コンパイル時間 3,413 ms
コンパイル使用メモリ 80,588 KB
実行使用メモリ 62,420 KB
最終ジャッジ日時 2023-08-26 23:50:50
合計ジャッジ時間 23,858 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 AC 123 ms
55,792 KB
testcase_02 AC 123 ms
55,860 KB
testcase_03 AC 124 ms
55,696 KB
testcase_04 AC 130 ms
55,532 KB
testcase_05 AC 766 ms
59,216 KB
testcase_06 AC 291 ms
59,564 KB
testcase_07 AC 121 ms
55,684 KB
testcase_08 AC 121 ms
55,956 KB
testcase_09 AC 123 ms
55,904 KB
testcase_10 AC 121 ms
55,580 KB
testcase_11 AC 809 ms
62,420 KB
testcase_12 AC 989 ms
61,644 KB
testcase_13 AC 914 ms
62,300 KB
testcase_14 AC 1,136 ms
62,016 KB
testcase_15 AC 1,323 ms
61,652 KB
testcase_16 AC 1,162 ms
61,936 KB
testcase_17 AC 1,689 ms
61,708 KB
testcase_18 AC 731 ms
61,648 KB
testcase_19 AC 1,252 ms
61,672 KB
testcase_20 AC 1,683 ms
61,244 KB
testcase_21 AC 1,649 ms
61,916 KB
testcase_22 AC 1,840 ms
61,932 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