結果

問題 No.165 四角で囲え！
ユーザー krotonkroton
提出日時 2014-12-30 22:04:48
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 259 ms / 5,000 ms
コード長 1,803 bytes
コンパイル時間 1,708 ms
コンパイル使用メモリ 153,500 KB
実行使用メモリ 7,732 KB
最終ジャッジ日時 2023-08-26 23:29:24
合計ジャッジ時間 5,174 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 141 ms
7,300 KB
testcase_01 AC 2 ms
5,416 KB
testcase_02 AC 2 ms
5,552 KB
testcase_03 AC 2 ms
5,516 KB
testcase_04 AC 2 ms
5,416 KB
testcase_05 AC 179 ms
7,272 KB
testcase_06 AC 33 ms
6,304 KB
testcase_07 AC 2 ms
5,440 KB
testcase_08 AC 2 ms
5,424 KB
testcase_09 AC 2 ms
5,416 KB
testcase_10 AC 2 ms
5,380 KB
testcase_11 AC 78 ms
6,760 KB
testcase_12 AC 35 ms
6,244 KB
testcase_13 AC 35 ms
6,300 KB
testcase_14 AC 25 ms
6,112 KB
testcase_15 AC 25 ms
6,168 KB
testcase_16 AC 259 ms
7,508 KB
testcase_17 AC 229 ms
7,584 KB
testcase_18 AC 188 ms
7,520 KB
testcase_19 AC 257 ms
7,488 KB
testcase_20 AC 233 ms
7,732 KB
testcase_21 AC 235 ms
7,576 KB
testcase_22 AC 235 ms
7,588 KB
権限があれば一括ダウンロードができます

ソースコード

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