結果

問題 No.165 四角で囲え！
ユーザー krotonkroton
提出日時 2014-12-30 21:59:12
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 1,803 bytes
コンパイル時間 1,339 ms
コンパイル使用メモリ 153,292 KB
実行使用メモリ 7,820 KB
最終ジャッジ日時 2023-09-03 20:18:39
合計ジャッジ時間 4,641 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 131 ms
7,008 KB
testcase_01 WA -
testcase_02 AC 2 ms
5,484 KB
testcase_03 AC 2 ms
5,492 KB
testcase_04 AC 2 ms
5,492 KB
testcase_05 AC 177 ms
7,280 KB
testcase_06 AC 30 ms
6,332 KB
testcase_07 AC 1 ms
5,516 KB
testcase_08 AC 2 ms
5,380 KB
testcase_09 AC 2 ms
5,412 KB
testcase_10 AC 2 ms
5,480 KB
testcase_11 WA -
testcase_12 AC 32 ms
6,544 KB
testcase_13 AC 32 ms
6,284 KB
testcase_14 WA -
testcase_15 AC 24 ms
6,456 KB
testcase_16 AC 253 ms
7,716 KB
testcase_17 AC 227 ms
7,596 KB
testcase_18 AC 187 ms
7,512 KB
testcase_19 AC 243 ms
7,568 KB
testcase_20 AC 231 ms
7,820 KB
testcase_21 AC 234 ms
7,552 KB
testcase_22 AC 228 ms
7,524 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[X[i]][Y[i]] = P[i];
		mat_c[X[i]][Y[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