結果
問題 | No.165 四角で囲え! |
ユーザー |
![]() |
提出日時 | 2015-03-12 23:54:09 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2,163 ms / 5,000 ms |
コード長 | 1,825 bytes |
コンパイル時間 | 2,367 ms |
コンパイル使用メモリ | 102,076 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-26 03:17:06 |
合計ジャッジ時間 | 26,920 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 19 |
ソースコード
#define _USE_MATH_DEFINES #include <algorithm> #include <cstdio> #include <functional> #include <iostream> #include <cfloat> #include <climits> #include <cstring> #include <cmath> #include <complex> #include <list> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <time.h> #include <vector> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> i_i; typedef pair<ll, int> ll_i; typedef pair<double, int> d_i; typedef pair<ll, ll> ll_ll; typedef pair<double, double> d_d; struct edge { int v, w; }; ll MOD = 1000000007; ll _MOD = 1000000009; double EPS = 1e-10; int main() { int N, B; cin >> N >> B; vector<pair<i_i, int> > a(N); for (int i = 0; i < N; i++) { int X, Y, P; cin >> X >> Y >> P; a[i] = make_pair(i_i(X, Y), P); } a.push_back(make_pair(i_i(1111111111, 0), 0)); sort(a.begin(), a.end()); int maxi = 0; for (int l = 0; l <= N; l++) for (int r = l; r <= N; r++) { map<int, int> m1, m2; for (int i = 0; i < N; i++) { int x = a[i].first.first; int y = a[i].first.second; int p = a[i].second; if (x >= a[l].first.first && x < a[r].first.first) { m1[y]++; m2[y] += p; } } vector<int> unko1, unko2; for (auto it = m1.begin(); it != m1.end(); it++) unko1.push_back(it->second); for (auto it = m2.begin(); it != m2.end(); it++) unko2.push_back(it->second); int n = unko1.size(); vector<int> unko3(n + 1), unko4(n + 1); for (int i = 1; i <= n; i++) { unko3[i] = unko3[i - 1] + unko1[i - 1]; unko4[i] = unko4[i - 1] + unko2[i - 1]; } int d = 0, sum = 0; for (int u = 0; u <= n; u++) { while (d + 1 <= n && unko4[d + 1] - unko4[u] <= B) d++; maxi = max(maxi, unko3[d] - unko3[u]); } } cout << maxi << endl; }