Submission #1371026

---

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) {
        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;
    long ans = 0;

    while (hi - lo > 1) {
        int mid = (hi + lo) / 2;
        long t_ans = 0;
        
        foreach (i; 0..MAX-mid-1) {
            foreach (j; 0..MAX-mid-1) {
                int a = cumsum(i, j, i+mid, j+mid);
                if (a >= K) {
                    (t_ans += comb(a, K)) %= MOD;
                }
            }
        }

        if (t_ans > 0) {
            hi = mid;
            ans = t_ans;
        } else {
            lo = mid;
        }
    }

    hi.writeln;
    ans.writeln;
    
}

Submission Info

Judge Result