結果
問題 | No.165 四角で囲え! |
ユーザー |
![]() |
提出日時 | 2015-03-13 00:02:23 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 281 ms / 5,000 ms |
コード長 | 1,944 bytes |
コンパイル時間 | 1,408 ms |
コンパイル使用メモリ | 114,996 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-26 03:14:48 |
合計ジャッジ時間 | 4,946 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 19 |
ソースコード
#define _USE_MATH_DEFINES #define _CRT_SECURE_NO_DEPRECATE #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <climits> #include <cfloat> #include <ctime> #include <cassert> #include <map> #include <utility> #include <set> #include <iostream> #include <memory> #include <string> #include <vector> #include <algorithm> #include <functional> #include <sstream> #include <complex> #include <stack> #include <queue> #include <numeric> #include <list> #include <iomanip> #include <fstream> #include <iterator> #include <bitset> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> Pii; typedef pair<ll, ll> Pll; #define FOR(i,n) for(int i = 0; i < (n); i++) #define sz(c) ((int)(c).size()) #define ten(x) ((int)1e##x) #define tenll(x) ((ll)1e##x) int compress(vector<int>& v){ vector<int> a = v; sort(a.begin(), a.end()); a.erase(unique(a.begin(), a.end()), a.end()); for (auto& x : v) x = lower_bound(a.begin(), a.end(), x) - a.begin(); return sz(a); } int main(){ int n, b; cin >> n >> b; b++; vector<int> xv, yv, pv; vector<tuple<int, int, int>> tp; FOR(i, n){ int x, y, p; cin >> x >> y >> p; tp.emplace_back(y, x, p); } sort(tp.begin(), tp.end()); for (auto a : tp) { int y, x, p; tie(y,x,p) = a; xv.push_back(x); yv.push_back(y); pv.push_back(p); } int len = compress(xv); compress(yv); int ans = 0; FOR(i, len){ for (int j = i; j < len; j++) { Pii cur[400] = {}; FOR(k, sz(xv)) if (i <= xv[k] && xv[k] <= j) { cur[yv[k]].first += 1; cur[yv[k]].second += pv[k]; } int r = 0, bsum = 0; int sm = 0; FOR(k, 400){ r = max(r, k); while (r < 400 && bsum + cur[r].second < b) { sm += cur[r].first; bsum += cur[r].second; r++; } if (sm > ans) { ans = sm; } if (sm) { bsum -= cur[k].second; sm -= cur[k].first; } } } } cout << ans << endl; }