結果
問題 | No.165 四角で囲え! |
ユーザー | nebukuro09 |
提出日時 | 2017-01-05 19:55:47 |
言語 | D (dmd 2.106.1) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,027 bytes |
コンパイル時間 | 804 ms |
コンパイル使用メモリ | 108,484 KB |
実行使用メモリ | 5,732 KB |
最終ジャッジ日時 | 2023-09-03 00:24:55 |
合計ジャッジ時間 | 4,317 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 104 ms
4,384 KB |
testcase_01 | AC | 1 ms
4,380 KB |
testcase_02 | AC | 1 ms
4,376 KB |
testcase_03 | WA | - |
testcase_04 | AC | 1 ms
4,380 KB |
testcase_05 | AC | 149 ms
5,148 KB |
testcase_06 | AC | 32 ms
4,380 KB |
testcase_07 | AC | 1 ms
4,380 KB |
testcase_08 | AC | 1 ms
4,376 KB |
testcase_09 | AC | 1 ms
4,376 KB |
testcase_10 | WA | - |
testcase_11 | AC | 131 ms
4,376 KB |
testcase_12 | AC | 168 ms
5,676 KB |
testcase_13 | AC | 179 ms
5,100 KB |
testcase_14 | AC | 176 ms
4,508 KB |
testcase_15 | AC | 168 ms
4,384 KB |
testcase_16 | AC | 216 ms
4,408 KB |
testcase_17 | AC | 165 ms
4,424 KB |
testcase_18 | AC | 214 ms
4,376 KB |
testcase_19 | AC | 185 ms
4,428 KB |
testcase_20 | AC | 164 ms
4,828 KB |
testcase_21 | AC | 163 ms
5,732 KB |
testcase_22 | AC | 163 ms
4,436 KB |
ソースコード
import std.stdio, std.array, std.string, std.conv, std.algorithm; import std.typecons, std.range, std.random, std.math, std.container; import std.numeric, std.bigint, core.bitop, core.stdc.stdio, std.bitmanip; int acm2d (ref int[][] acm, int r1, int c1, int r2, int c2) { return acm[r2+1][c2+1] - acm[r2+1][c1] - acm[r1][c2+1] + acm[r1][c1]; } void main() { alias Tuple!(int, "x", int, "y", int, "p") Point; int N, B; Point[] p; scanf("%d %d", &N, &B); p = new Point[](N); foreach (i; 0..N) { int x, y, po; scanf("%d %d %d", &x, &y, &po); p[i] = Point(x, y, po); } p.sort!"a.x < b.x"(); int prev = p[0].x; p[0].x = 0; foreach (i; 1..N) { int cur = p[i].x; p[i].x = (p[i].x == prev) ? p[i-1].x : p[i-1].x + 1; prev = cur; } p.sort!"a.y < b.y"(); prev = p[0].y; p[0].y = 0; foreach (i; 1..N) { int cur = p[i].y; p[i].y = (p[i].y == prev) ? p[i-1].y : p[i-1].y + 1; prev = cur; } auto acm_score = new int[][](N+1, N+1); auto acm_exist = new int[][](N+1, N+1); foreach (i; 0..N) { acm_score[p[i].x+1][p[i].y+1] = p[i].p; acm_exist[p[i].x+1][p[i].y+1] = 1; } foreach (i; 0..N+1) { foreach (j; 0..N) { acm_score[i][j+1] += acm_score[i][j]; acm_exist[i][j+1] += acm_exist[i][j]; } } foreach (j; 0..N+1) { foreach (i; 0..N) { acm_score[i+1][j] += acm_score[i][j]; acm_exist[i+1][j] += acm_exist[i][j]; } } int ans = 0; foreach (r1; 0..N) { foreach (r2; r1+1..N) { int c1, c2; while (c2 < N) { if (acm2d(acm_score, r1, c1, r2, c2) <= B) { ans = max(ans, acm2d(acm_exist, r1, c1, r2, c2)); c2++; } else{ c1++; if (c2 < c1) c2 = c1; } } } } ans.writeln; }