結果
問題 |
No.165 四角で囲え!
|
ユーザー |
![]() |
提出日時 | 2016-03-24 12:02:54 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 163 ms / 5,000 ms |
コード長 | 2,184 bytes |
コンパイル時間 | 1,018 ms |
コンパイル使用メモリ | 94,748 KB |
実行使用メモリ | 6,144 KB |
最終ジャッジ日時 | 2024-12-26 03:36:58 |
合計ジャッジ時間 | 2,799 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 19 |
ソースコード
/* -*- coding: utf-8 -*- * * 165.cc: No.165 四角で囲え! - yukicoder */ #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<string> #include<vector> #include<map> #include<set> #include<stack> #include<list> #include<queue> #include<deque> #include<algorithm> #include<numeric> #include<utility> #include<complex> #include<functional> using namespace std; /* constant */ const int MAX_N = 400; /* typedef */ typedef map<int,int> mii; /* global variables */ int xs[MAX_N], ys[MAX_N], ps[MAX_N]; int xv[MAX_N], yv[MAX_N]; mii xmap, ymap; int cs[MAX_N][MAX_N], csums[MAX_N + 1][MAX_N + 1]; int pas[MAX_N][MAX_N], psums[MAX_N + 1][MAX_N + 1]; /* subroutines */ inline int getcsum(int x0, int y0, int x1, int y1) { // [x0,x1), [y0,y1) return csums[y1][x1] - csums[y1][x0] - csums[y0][x1] + csums[y0][x0]; } inline int getpsum(int x0, int y0, int x1, int y1) { // [x0,x1), [y0,y1) return psums[y1][x1] - psums[y1][x0] - psums[y0][x1] + psums[y0][x0]; } /* main */ int main() { int n, b; cin >> n >> b; for (int i = 0; i < n; i++) { cin >> xs[i] >> ys[i] >> ps[i]; xv[i] = xs[i], yv[i] = ys[i]; } sort(xv, xv + n); int xn = unique(xv, xv + n) - xv; sort(yv, yv + n); int yn = unique(yv, yv + n) - yv; //printf("xn=%d,yn=%d\n", xn, yn); for (int i = 0; i < xn; i++) xmap[xv[i]] = i; for (int i = 0; i < yn; i++) ymap[yv[i]] = i; for (int i = 0; i < n; i++) { int gx = xmap[xs[i]], gy = ymap[ys[i]]; cs[gy][gx] = 1; pas[gy][gx] = ps[i]; } for (int gy = 0; gy < yn; gy++) for (int gx = 0; gx < xn; gx++) { csums[gy + 1][gx + 1] = cs[gy][gx] + csums[gy + 1][gx] + csums[gy][gx + 1] - csums[gy][gx]; psums[gy + 1][gx + 1] = pas[gy][gx] + psums[gy + 1][gx] + psums[gy][gx + 1] - psums[gy][gx]; } int maxc = 0; for (int gy0 = 0; gy0 < yn; gy0++) for (int gy1 = gy0 + 1; gy1 <= yn; gy1++) { int sum = 0; for (int gx0 = 0, gx1 = 0; gx1 <= xn; gx0++) { while (gx1 <= xn && getpsum(gx0, gy0, gx1, gy1) <= b) gx1++; int c = getcsum(gx0, gy0, gx1 - 1, gy1); if (maxc < c) maxc = c; } } printf("%d\n", maxc); return 0; }