Skip to content

Instantly share code, notes, and snippets.

@ia7ck
Created October 30, 2016 07:09
Show Gist options
  • Save ia7ck/2a7c2a99c882267de07f483b1c854355 to your computer and use it in GitHub Desktop.
Save ia7ck/2a7c2a99c882267de07f483b1c854355 to your computer and use it in GitHub Desktop.
ABC 023-C 収集王
#include<iostream>
#include<vector>
#include<stdio.h>
#define rep(i, n) for(int i=0; i<(n); i++)
#define pb push_back
using namespace std;
int main(){
int R, C, K, N;
cin>> R>> C>> K>> N;
vector<int> r, c;
rep(i, N){
int a, b;
scanf("%d %d", &a, &b);
a--; b--;
r.pb(a); c.pb(b);
}
vector<int> row(R, 0), col(C, 0);
rep(i, N){
row[r[i]]++;
col[c[i]]++;
}
vector<pair<int, int> > cd(N+1, make_pair(0, 0));// <raw, col>
rep(i, R) cd[row[i]].first++;
rep(j, C) cd[col[j]].second++;
long long ans=0;
for(int i=0; i<=K; i++){
ans+=cd[i].first*cd[K-i].second;
}
rep(i, N){
if(row[r[i]]+col[c[i]]==K+1) ans++;
if(row[r[i]]+col[c[i]]==K) ans--;
}
cout<< ans<< endl;
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment