Submission #1371089
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 int MAX2 = 10^^5 + 7;
immutable long MOD = 10^^9 + 7;
void main() {
auto modinv = new long[](MAX2);
modinv[0] = modinv[1] = 1;
foreach(i; 2..MAX2) {
modinv[i] = modinv[MOD % i] * (MOD - MOD / i) % MOD;
}
auto f_mod = new long[](MAX2);
auto f_modinv = new long[](MAX2);
f_mod[0] = f_mod[1] = 1;
f_modinv[0] = f_modinv[1] = 1;
foreach(i; 2..MAX2) {
f_mod[i] = (i * f_mod[i-1]) % MOD;
f_modinv[i] = (modinv[i] * f_modinv[i-1]) % MOD;
}
long comb(int n, int k) {
if (n < k) return 0;
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);
auto C = new int[][](MAX, MAX);
foreach (i; 0..N) {
s = readln.split.map!(to!int);
X[i] = s[0];
Y[i] = s[1];
C[s[0]+1][s[1]+1] += 1;
}
foreach (i; 0..MAX) foreach (j; 0..MAX-1) C[i][j+1] += C[i][j];
foreach (j; 0..MAX) foreach (i; 0..MAX-1) C[i+1][j] += C[i][j];
int cumsum(int x1, int y1, int x2, int y2) {
return C[x2+1][y2+1] - C[x2+1][y1] - C[x1][y2+1] + C[x1][y1];
}
int hi = 3000;
int lo = -1;
while (hi - lo > 1) {
int mid = (hi + lo) / 2;
bool ok = false;
foreach (i; 0..MAX-mid-1) {
foreach (j; 0..MAX-mid-1) {
int a = cumsum(i, j, i+mid, j+mid);
if (a >= K) {
ok = true;
break;
}
}
if (ok) break;
}
if (ok) hi = mid;
else lo = mid;
}
long cnt = 0;
foreach (i; 0..MAX-hi-1) {
foreach (j; 0..MAX-hi-1) {
int a = cumsum(i, j, i+hi, j+hi);
if (a < K) continue;
int b = cumsum(i+1, j, i+hi, j+hi);
int c = cumsum(i, j+1, i+hi, j+hi);
int d = cumsum(i, j, i, j);
if (d > 0) cnt += comb(a, K) - comb(a-d, K);
else cnt += comb(a-d, K) - comb(a-b, K) - comb(a-c, K) + comb(a-b-c+d, K);
cnt = (cnt % MOD + MOD) % MOD;
}
}
hi.writeln;
cnt.writeln;
}
Submission Info
Submission Time |
|
Task |
D - アットコーダーモンスターズ |
User |
nebukuro09 |
Language |
D (LDC 0.17.0) |
Score |
0 |
Code Size |
2528 Byte |
Status |
WA |
Exec Time |
507 ms |
Memory |
41852 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 |
187 ms |
39804 KB |
subtask0_sample_02.txt |
AC |
330 ms |
39292 KB |
subtask0_sample_03.txt |
AC |
150 ms |
39036 KB |
subtask0_sample_04.txt |
AC |
507 ms |
39676 KB |
subtask1_random01.txt |
AC |
264 ms |
39292 KB |
subtask1_random02.txt |
AC |
150 ms |
38396 KB |
subtask1_random03.txt |
AC |
188 ms |
38268 KB |
subtask1_random04.txt |
AC |
188 ms |
38908 KB |
subtask1_random05.txt |
WA |
189 ms |
38140 KB |
subtask1_random06.txt |
WA |
264 ms |
38524 KB |
subtask1_random07.txt |
AC |
141 ms |
39292 KB |
subtask1_random08.txt |
AC |
150 ms |
39036 KB |
subtask1_random09.txt |
AC |
227 ms |
38652 KB |
subtask1_random10.txt |
AC |
187 ms |
39420 KB |
subtask2_random01.txt |
AC |
357 ms |
41852 KB |
subtask2_random02.txt |
WA |
204 ms |
39932 KB |
subtask2_random03.txt |
WA |
196 ms |
41340 KB |
subtask2_random04.txt |
WA |
204 ms |
41596 KB |
subtask2_random05.txt |
WA |
202 ms |
41596 KB |
subtask2_random06.txt |
AC |
217 ms |
41084 KB |
subtask2_random07.txt |
AC |
192 ms |
41084 KB |
subtask2_random08.txt |
AC |
254 ms |
41084 KB |
subtask2_random09.txt |
WA |
194 ms |
41724 KB |
subtask2_random10.txt |
WA |
225 ms |
41596 KB |
subtask2_random11.txt |
WA |
370 ms |
41852 KB |
subtask2_random12.txt |
AC |
434 ms |
40316 KB |
subtask2_random13.txt |
WA |
298 ms |
41596 KB |
subtask2_random14.txt |
AC |
428 ms |
39932 KB |
subtask2_random15.txt |
AC |
360 ms |
40316 KB |
subtask2_random16.txt |
WA |
313 ms |
40444 KB |
subtask2_random17.txt |
WA |
353 ms |
40060 KB |
subtask2_random18.txt |
WA |
352 ms |
41212 KB |
subtask2_random19.txt |
WA |
316 ms |
41724 KB |
subtask2_random20.txt |
WA |
392 ms |
41596 KB |
subtask2_special01.txt |
AC |
190 ms |
41212 KB |
subtask2_special02.txt |
WA |
219 ms |
41596 KB |
subtask2_special03.txt |
AC |
222 ms |
40060 KB |
subtask2_special04.txt |
AC |
198 ms |
40188 KB |
subtask2_special05.txt |
AC |
196 ms |
41084 KB |
subtask2_special06.txt |
AC |
236 ms |
40188 KB |
subtask2_special07.txt |
AC |
237 ms |
41724 KB |