#7956 (C++11) No.165 四角で囲え！

• 問題: No.165 四角で囲え！
• ユーザー: kroton
• 提出日時: 2014-12-30 22:04:48
• 言語: C++11 (gcc 11.4.0)
• 結果: AC
• 実行時間: 237 ms / 5,000 ms
• コード長: 1,803 bytes
• コンパイル時間: 1,641 ms
• コンパイル使用メモリ: 167,168 KB
• 実行使用メモリ: 7,168 KB
• 最終ジャッジ日時: 2024-06-07 18:52:04
• 合計ジャッジ時間: 4,940 ms
• ジャッジサーバーID （参考情報）: judge1 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	123 ms; 6,016 KB
testcase_01	AC	1 ms; 5,376 KB
testcase_02	AC	1 ms; 5,376 KB
testcase_03	AC	2 ms; 5,376 KB
testcase_04	AC	1 ms; 5,376 KB
testcase_05	AC	167 ms; 6,400 KB
testcase_06	AC	31 ms; 5,376 KB
testcase_07	AC	2 ms; 5,376 KB
testcase_08	AC	1 ms; 5,376 KB
testcase_09	AC	2 ms; 5,376 KB
testcase_10	AC	2 ms; 5,376 KB
testcase_11	AC	71 ms; 5,888 KB
testcase_12	AC	30 ms; 5,376 KB
testcase_13	AC	30 ms; 5,376 KB
testcase_14	AC	24 ms; 5,376 KB
testcase_15	AC	24 ms; 5,376 KB
testcase_16	AC	237 ms; 6,784 KB
testcase_17	AC	194 ms; 7,168 KB
testcase_18	AC	172 ms; 7,040 KB
testcase_19	AC	222 ms; 6,912 KB
testcase_20	AC	209 ms; 6,912 KB
testcase_21	AC	202 ms; 6,912 KB
testcase_22	AC	201 ms; 6,912 KB

ソースコード

#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;
}