結果

問題 No.165 四角で囲え！
コンテスト
ユーザー uafr_cs
提出日時 2017-11-09 13:28:38
言語 Java
(openjdk 23)
結果
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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 18 WA * 1
権限があれば一括ダウンロードができます

ソースコード

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