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
AC × 4
AC × 11
WA × 2
AC × 25
WA × 16
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