結果

問題 No.165 四角で囲え！
コンテスト
ユーザー ゴリポン先生
提出日時 2025-12-19 19:21:43
言語 D
(dmd 2.111.0)
結果
AC  
実行時間 573 ms / 5,000 ms
コード長 1,924 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 5,775 ms
コンパイル使用メモリ 222,476 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-12-19 19:21:54
合計ジャッジ時間 8,266 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

module main;
// https://kenkoooo.hatenablog.com/entry/2015/03/14/030253 より
// 座標圧縮、尺取り法
import std;

// STLのlower_boundのようなもの
int lowerBound(T)(T[] arr, in T value)
{
	int first = 0, last = arr.length.to!int;
	for (int len = last; len != 0;) {
		int half = len >> 1, mid = first + half;
		if (arr[mid] < value) {
			len -= half + 1;
			first = mid + 1;
		} else
			len = half;
	}
	return first;
}

void main()
{
	// 入力
	int N;
	long B;
	readln.chomp.formattedRead("%d %d", N, B);
	auto X = new int[](N), Y = new int[](N), P = new int[](N);
	foreach (ref x, ref y, ref p; lockstep(X, Y, P)) {
		readln.chomp.formattedRead("%d %d %d", x, y, p);
	}
	// 答えの計算
	auto xSet = redBlackTree(X), ySet = redBlackTree(Y);
	xSet.insert(int.min);
	xSet.insert(int.max);
	ySet.insert(int.min);
	ySet.insert(int.max);

	auto xIntegers = xSet.array, yIntegers = ySet.array;

	int W = xSet.length.to!int, H = ySet.length.to!int;
	// 宝の数と得点の累積和
	auto treasures = new int[][](H + 1, W + 1);
	auto tPoints = new int[][](H + 1, W + 1);
	foreach (i; 0 .. N) {
		int x = lowerBound(xIntegers, X[i]);
		int y = lowerBound(yIntegers, Y[i]);
		treasures[y + 1][x + 1]++;
		tPoints[y + 1][x + 1] += P[i];
	}

	foreach (i; 0 .. H) {
		foreach (j; 0 .. W) {
			treasures[i + 1][j + 1] += treasures[i + 1][j] + treasures[i][j + 1] - treasures[i][j];
			tPoints[i + 1][j + 1] += tPoints[i + 1][j] + tPoints[i][j + 1] - tPoints[i][j];
		}
	}

	int ans = 0;
	foreach (x1; 0 .. W) {
		foreach (x2; x1 + 1 .. W + 1) {
			int y1 = 0, y2 = 1;
			while (y2 < H + 1) {
				int tNum = treasures[y2][x2] - treasures[y1][x2] - treasures[y2][x1] + treasures[y1][x1];
				int pointNum = tPoints[y2][x2] - tPoints[y1][x2] - tPoints[y2][x1] + tPoints[y1][x1];
				if (pointNum <= B) {
					ans =max(ans, tNum);
					y2++;
				} else {
					y1++;
				}
			}
		}
	}
	// 答えの出力
	writeln(ans);
}
0