結果

問題 No.165 四角で囲え！
ユーザー krotonkroton
提出日時 2014-12-30 22:04:48
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 255 ms / 5,000 ms
コード長 1,803 bytes
コンパイル時間 2,034 ms
コンパイル使用メモリ 166,384 KB
実行使用メモリ 7,040 KB
最終ジャッジ日時 2024-12-26 03:11:33
合計ジャッジ時間 5,263 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
const int SIZE = 555;

int N, B;
int X[SIZE], Y[SIZE], P[SIZE];

int mat_p[SIZE][SIZE], dp_p[SIZE][SIZE];
int mat_c[SIZE][SIZE], dp_c[SIZE][SIZE];

void compress(){
	map<int, int> xs, ys;
	for(int i=0;i<N;i++){
		xs[X[i]] = 1;
		ys[Y[i]] = 1;
	}

	int cnt = 0;
	for(auto &x : xs)x.second = cnt++;

	cnt = 0;
	for(auto &y : ys)y.second = cnt++;

	for(int i=0;i<N;i++){
		X[i] = xs[X[i]];
		Y[i] = ys[Y[i]];
	}
}

void calc_dp(int H, int W, int mat[SIZE][SIZE], int dp[SIZE][SIZE]){
	dp[0][0] = mat[0][0];
	for(int x=1;x<W;x++){
		dp[0][x] = dp[0][x-1] + mat[0][x];
	}
	for(int y=1;y<H;y++){
		dp[y][0] = dp[y-1][0] + mat[y][0];
	}
	for(int y=1;y<H;y++)for(int x=1;x<W;x++){
		dp[y][x] = dp[y-1][x] + dp[y][x-1] - dp[y-1][x-1] + mat[y][x];
	}
}

inline int calc_range(int y, int x, int h, int w, int dp[SIZE][SIZE]){
	int res = dp[y+h-1][x+w-1];
	if(y - 1 >= 0)res -= dp[y-1][x+w-1];
	if(x - 1 >= 0)res -= dp[y+h-1][x-1];
	if(y - 1 >= 0 && x - 1 >= 0){
		res += dp[y-1][x-1];
	}
	return res;
}

int solve(){
	compress();

	int H = 0, W = 0;
	for(int i=0;i<N;i++){
		H = max(H, Y[i]);
		W = max(W, X[i]);
	}

	++H;
	++W;

	for(int i=0;i<N;i++){
		mat_p[Y[i]][X[i]] = P[i];
		mat_c[Y[i]][X[i]] = 1;
	}

	calc_dp(H, W, mat_p, dp_p);
	calc_dp(H, W, mat_c, dp_c);

	int res = 0;
	for(int y=0;y<H;y++)for(int x=0;x<W;x++){
		int ws = 0;
		for(int w=1;x+w-1<W;w++){
			int b = calc_range(y, x, 1, w, dp_p);
			if(b <= B){
				ws = w;
			} else {
				break;
			}
		}
		for(int h=1;y+h-1<H;h++){
			while(ws > 0 && calc_range(y, x, h, ws, dp_p) > B)--ws;
			if(ws == 0)break;

			res = max(res, calc_range(y, x, h, ws, dp_c));
		}
	}

	return res;
}

int main(){
	cin >> N >> B;
	for(int i=0;i<N;i++)cin >> X[i] >> Y[i] >> P[i];

	cout << solve() << endl;
	return 0;
}
0