#1182326 (C++23) No.165 四角で囲え！

• 問題: No.165 四角で囲え！
• ユーザー: aruudo
• 提出日時: 2026-09-04 09:37:54
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0)
• 結果: AC
• 実行時間: 139 ms / 5,000 ms
• コード長: 1,651 bytes
• コンパイル時間: 2,591 ms
• コンパイル使用メモリ: 359,308 KB
• 実行使用メモリ: 6,272 KB
• 最終ジャッジ日時: 2026-09-04 09:38:02
• 合計ジャッジ時間: 5,326 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_0

ファイルパターン	結果
sample	AC * 4
other	AC * 19

ソースコード

#include <bits/stdc++.h> 

using i64 = long long; 
using u64 = unsigned long long; 
using u32 = unsigned; 

using u128 = unsigned __int128; 
using i128 = __int128; 

void solve() {
	int N, B; std::cin >> N >> B;
	std::map<i64, std::vector<std::pair<i64, i64>>> m;
	std::vector<i64> uy;
	for(int i = 0; i < N; i ++) {
		i64 x, y, p; std::cin >> x >> y >> p;
		m[x].push_back({y, p});
		uy.push_back(y);
	}

	std::sort(uy.begin(), uy.end());
	uy.erase(std::unique(uy.begin(), uy.end()), uy.end());

	int nx = (int)m.size(), ny = (int)uy.size();

	std::vector scores (nx, std::vector<i64> (ny + 1));
	std::vector points (nx, std::vector<int> (ny + 1));

	int ix = 0;
	for(auto const& [x, point] : m) {
		for(auto const& p : point) {
			int i = std::lower_bound(uy.begin(), uy.end(), p.first) - uy.begin() + 1;
			scores[ix][i] += p.second;
			points[ix][i] ++;
		}
		ix++;
	}

	for(int i = 0; i < nx; i ++) {
		for(int j = 1; j < ny + 1; j ++) {
			scores[i][j] += scores[i][j - 1];
			points[i][j] += points[i][j - 1];
		}
	}

	int max = -1;
	for(int i = 1; i < ny + 1; i ++) {
		for(int j = i; j < ny + 1; j ++) {
			i64 score = 0;
			int cur = 0;
			int l = 0, r = 0;
			while(r < nx) {
				score += scores[r][j] - scores[r][i - 1];
				cur += points[r][j] - points[r][i - 1];
				while(score > B && l <= r) {
					score -= scores[l][j] - scores[l][i - 1];
					cur -= points[l][j] - points[l][i - 1];
					l ++;
				}
				max = std::max(max, cur);
				r ++;
			}
		}
	}
	
	std::cout << max;

} 

int main() { 
	std::ios::sync_with_stdio(false); 
	std::cin.tie(nullptr); 

	int T = 1; 
	//std::cin >> T; 

	while (T--) { 
		solve(); 
	} 
	return 0; 
}