結果

問題 No.165 四角で囲え！
ユーザー krotonkroton
提出日時 2014-12-30 21:59:12
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 1,803 bytes
コンパイル時間 1,382 ms
コンパイル使用メモリ 167,116 KB
実行使用メモリ 7,660 KB
最終ジャッジ日時 2024-06-13 01:08:28
合計ジャッジ時間 4,323 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 117 ms
7,164 KB
testcase_01 WA -
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 2 ms
6,944 KB
testcase_05 AC 163 ms
7,160 KB
testcase_06 AC 30 ms
6,944 KB
testcase_07 AC 2 ms
6,944 KB
testcase_08 AC 2 ms
6,944 KB
testcase_09 AC 3 ms
7,632 KB
testcase_10 AC 2 ms
6,944 KB
testcase_11 WA -
testcase_12 AC 30 ms
6,944 KB
testcase_13 AC 29 ms
7,660 KB
testcase_14 WA -
testcase_15 AC 23 ms
6,944 KB
testcase_16 AC 229 ms
7,292 KB
testcase_17 AC 198 ms
7,420 KB
testcase_18 AC 174 ms
7,420 KB
testcase_19 AC 216 ms
7,040 KB
testcase_20 AC 202 ms
7,292 KB
testcase_21 AC 201 ms
7,420 KB
testcase_22 AC 200 ms
7,416 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