Submission #1482038

---

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>

using namespace std;
using llng = long long;
template<typename T> using v = vector<T>;
template<typename T> using vv = v<v<T> >;

int main() {
    int R, C, K; cin >> R >> C >> K;
    int N; cin >> N;
    v<int> r(N), c(N);
    v<int> r_count(R+1), c_count(C+1);
    for (int i=0; i<N; i++) {
        cin >> r[i] >> c[i]; r_count[r[i]]++; c_count[c[i]]++;
    }

    v<int> count_r(R+1), count_c(C+1);
    for (int r=1; r<=R; r++) count_r[r_count[r]]++;
    for (int c=1; c<=C; c++) count_c[c_count[c]]++;

    llng ans = 0;
    for (int k=0; k<=K; k++) if (k <= R && K-k <= C){
        ans += count_r[k] * count_c[K-k];
    }
    for (int i=0; i<N; i++) {
        if (r_count[r[i]] + c_count[c[i]] == K) ans--;
        if (r_count[r[i]] + c_count[c[i]] == K+1) ans++;
    }
    cout << ans << endl;
    return 0;
}

Submission Info

Judge Result