Submission #1218413
Source Code Expand
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; immutable int MAX = 3010; immutable long MOD = 10^^9+7; void main() { immutable int MMAX = 2*10^^6+1; auto modinv = new long[](MMAX); modinv[0] = modinv[1] = 1; foreach(i; 2..MAX) { modinv[i] = modinv[MOD % i] * (MOD - MOD / i) % MOD; } auto f_mod = new long[](MMAX); auto f_modinv = new long[](MMAX); f_mod[0] = f_mod[1] = 1; f_modinv[0] = f_modinv[1] = 1; foreach(i; 2..MMAX) { f_mod[i] = (i * f_mod[i-1]) % MOD; f_modinv[i] = (modinv[i] * f_modinv[i-1]) % MOD; } long combi(int n, int k) { return f_mod[n] * f_modinv[n-k] % MOD * f_modinv[k] % MOD; } auto s = readln.split.map!(to!int); auto N = s[0]; auto K = s[1]; auto X = new int[](N); auto Y = new int[](N); foreach (i; 0..N) { s = readln.split.map!(to!int); X[i] = s[0]; Y[i] = s[1]; } auto A = new int[][](MAX+1, MAX+1); foreach (i; 0..N) A[X[i]+1][Y[i]+1] += 1; foreach (i; 0..MAX+1) foreach (j; 0..MAX) A[i][j+1] += A[i][j]; foreach (j; 0..MAX+1) foreach (i; 0..MAX) A[i+1][j] += A[i][j]; int cumsum(int x1, int y1, int x2, int y2) { return A[x2+1][y2+1] - A[x2+1][y1] - A[x1][y2+1] + A[x1][y1]; } bool count(int x) { foreach (i; 0..MAX-x) foreach (j; 0..MAX-x) if (cumsum(i, j, i+x, j+x) >= K) return true; return false; } int hi = MAX; int lo = -1; while (hi - lo > 1) { int mid = (hi + lo) / 2; if (count(mid)) hi = mid; else lo = mid; } long ans = 0; int cs; foreach (i; 0..MAX-hi) foreach (j; 0..MAX-hi) if ((cs = cumsum(i, j, i+hi, j+hi)) >= K) ans = (ans + combi(cs, K)) % MOD; hi.writeln; ans.writeln; }
Submission Info
Submission Time | |
---|---|
Task | D - アットコーダーモンスターズ |
User | nebukuro09 |
Language | D (LDC 0.17.0) |
Score | 0 |
Code Size | 2139 Byte |
Status | WA |
Exec Time | 487 ms |
Memory | 71548 KB |
Judge Result
Set Name | Sample | Subtask1 | All | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 10 | 0 / 90 | ||||||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Sample | subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask0_sample_04.txt |
Subtask1 | subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask1_random01.txt, subtask1_random02.txt, subtask1_random03.txt, subtask1_random04.txt, subtask1_random05.txt, subtask1_random06.txt, subtask1_random07.txt, subtask1_random08.txt, subtask1_random09.txt, subtask1_random10.txt |
All | subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask0_sample_04.txt, subtask1_random01.txt, subtask1_random02.txt, subtask1_random03.txt, subtask1_random04.txt, subtask1_random05.txt, subtask1_random06.txt, subtask1_random07.txt, subtask1_random08.txt, subtask1_random09.txt, subtask1_random10.txt, subtask2_random01.txt, subtask2_random02.txt, subtask2_random03.txt, subtask2_random04.txt, subtask2_random05.txt, subtask2_random06.txt, subtask2_random07.txt, subtask2_random08.txt, subtask2_random09.txt, subtask2_random10.txt, subtask2_random11.txt, subtask2_random12.txt, subtask2_random13.txt, subtask2_random14.txt, subtask2_random15.txt, subtask2_random16.txt, subtask2_random17.txt, subtask2_random18.txt, subtask2_random19.txt, subtask2_random20.txt, subtask2_special01.txt, subtask2_special02.txt, subtask2_special03.txt, subtask2_special04.txt, subtask2_special05.txt, subtask2_special06.txt, subtask2_special07.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
subtask0_sample_01.txt | AC | 192 ms | 70652 KB |
subtask0_sample_02.txt | AC | 355 ms | 70652 KB |
subtask0_sample_03.txt | AC | 156 ms | 70652 KB |
subtask0_sample_04.txt | AC | 487 ms | 70652 KB |
subtask1_random01.txt | AC | 262 ms | 70652 KB |
subtask1_random02.txt | AC | 157 ms | 70652 KB |
subtask1_random03.txt | AC | 192 ms | 70652 KB |
subtask1_random04.txt | AC | 191 ms | 70652 KB |
subtask1_random05.txt | WA | 190 ms | 70652 KB |
subtask1_random06.txt | WA | 262 ms | 70652 KB |
subtask1_random07.txt | AC | 156 ms | 70652 KB |
subtask1_random08.txt | AC | 155 ms | 70652 KB |
subtask1_random09.txt | AC | 226 ms | 70652 KB |
subtask1_random10.txt | AC | 190 ms | 70652 KB |
subtask2_random01.txt | WA | 318 ms | 71164 KB |
subtask2_random02.txt | WA | 197 ms | 69756 KB |
subtask2_random03.txt | WA | 187 ms | 70268 KB |
subtask2_random04.txt | WA | 190 ms | 70396 KB |
subtask2_random05.txt | WA | 193 ms | 69756 KB |
subtask2_random06.txt | WA | 304 ms | 70780 KB |
subtask2_random07.txt | WA | 185 ms | 70268 KB |
subtask2_random08.txt | WA | 346 ms | 70780 KB |
subtask2_random09.txt | WA | 184 ms | 71292 KB |
subtask2_random10.txt | WA | 213 ms | 70908 KB |
subtask2_random11.txt | WA | 385 ms | 70780 KB |
subtask2_random12.txt | AC | 387 ms | 70908 KB |
subtask2_random13.txt | WA | 283 ms | 70140 KB |
subtask2_random14.txt | AC | 380 ms | 71164 KB |
subtask2_random15.txt | AC | 308 ms | 70396 KB |
subtask2_random16.txt | WA | 310 ms | 71420 KB |
subtask2_random17.txt | WA | 307 ms | 70908 KB |
subtask2_random18.txt | WA | 342 ms | 70012 KB |
subtask2_random19.txt | WA | 271 ms | 71164 KB |
subtask2_random20.txt | WA | 386 ms | 71548 KB |
subtask2_special01.txt | WA | 185 ms | 70780 KB |
subtask2_special02.txt | WA | 212 ms | 70012 KB |
subtask2_special03.txt | AC | 211 ms | 70652 KB |
subtask2_special04.txt | WA | 201 ms | 69756 KB |
subtask2_special05.txt | WA | 200 ms | 70908 KB |
subtask2_special06.txt | WA | 236 ms | 70908 KB |
subtask2_special07.txt | WA | 236 ms | 70652 KB |