結果

問題 No.165 四角で囲え！
ユーザー scache
提出日時 2015-05-27 11:34:06
言語 Java
(openjdk 23)
結果
WA  
実行時間 -
コード長 1,827 bytes
コンパイル時間 3,196 ms
コンパイル使用メモリ 80,188 KB
実行使用メモリ 45,492 KB
最終ジャッジ日時 2024-07-06 10:38:56
合計ジャッジ時間 11,755 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 11 WA * 8
権限があれば一括ダウンロードができます

ソースコード

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<ia.length;i++)
            cx[i] = Arrays.binarySearch(ia, x[i]);
        
        return cx;
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0