結果

問題 No.165 四角で囲え！
ユーザー uafr_csuafr_cs
提出日時 2017-11-09 13:28:38
言語 Java21
(openjdk 21)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 2,838 bytes
コンパイル時間 3,623 ms
コンパイル使用メモリ 79,192 KB
実行使用メモリ 48,536 KB
最終ジャッジ日時 2024-12-26 03:41:10
合計ジャッジ時間 24,849 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 AC 163 ms
41,300 KB
testcase_02 AC 158 ms
41,124 KB
testcase_03 AC 154 ms
41,136 KB
testcase_04 AC 165 ms
41,352 KB
testcase_05 AC 1,022 ms
45,264 KB
testcase_06 AC 410 ms
43,580 KB
testcase_07 AC 157 ms
41,252 KB
testcase_08 AC 166 ms
41,136 KB
testcase_09 AC 156 ms
41,044 KB
testcase_10 AC 163 ms
41,316 KB
testcase_11 AC 1,022 ms
45,316 KB
testcase_12 AC 1,123 ms
48,392 KB
testcase_13 AC 1,103 ms
48,212 KB
testcase_14 AC 1,466 ms
48,536 KB
testcase_15 AC 1,578 ms
48,288 KB
testcase_16 AC 1,498 ms
48,400 KB
testcase_17 AC 1,523 ms
48,036 KB
testcase_18 AC 1,035 ms
48,216 KB
testcase_19 AC 1,491 ms
48,512 KB
testcase_20 AC 1,574 ms
47,888 KB
testcase_21 AC 1,416 ms
48,032 KB
testcase_22 AC 1,560 ms
48,464 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