Submission #47652900

---

Source Code Expand

#include <bits/stdc++.h>
#include <atcoder/modint>

namespace {
using ModInt [[maybe_unused]] = atcoder::modint998244353;
using Num [[maybe_unused]] = long long int;
using Vec [[maybe_unused]] = std::vector<Num>;
using Set [[maybe_unused]] = std::set<Num>;
using Mset [[maybe_unused]] = std::multiset<Num>;
using Edges [[maybe_unused]] = std::vector<std::vector<Num>>;

template<typename T>
using Q [[maybe_unused]] = std::queue<T>;

template<typename T>
using PQ [[maybe_unused]] = std::priority_queue<T, std::vector<T>, std::greater<T>>;
}

constexpr Num MaxHeight = 5000;
constexpr Num MaxWeight = 5000;
Num grid[MaxHeight + 1][MaxWeight + 1];

void solve(std::istream& is, std::ostream& os) {
    Num n, k;
    is >> n >> k;

    for(Num i{0}; i<n; ++i) {
        Num h, w;
        is >> h >> w;
        grid[h][w] += 1;
    }

    for(Num h{0}; h<=MaxHeight; ++h) {
        for(Num w{1}; w<=MaxWeight; ++w) {
            grid[h][w] += grid[h][w-1];
        }
    }

    for(Num w{0}; w<=MaxWeight; ++w) {
        for(Num h{1}; h<=MaxHeight; ++h) {
            grid[h][w] += grid[h-1][w];
        }
    }

    Num answer {0};
    for(Num h{k+1}; h<=MaxHeight; ++h) {
        for(Num w{k+1}; w<=MaxWeight; ++w) {
            answer = std::max(answer, grid[w][h] - grid[w-k-1][h] - grid[w][h-k-1] + grid[w-k-1][h-k-1]);
        }
    }

    os << answer << "\n";
}

int main(void) {
    solve(std::cin, std::cout);
    return 0;
}

Submission Info

Judge Result