Submission #1518432


Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, pii> pip;
const ll INF = 1ll<<29;
const ll MOD = 1000000007;
const double EPS  = 1e-10;
const bool debug = 0;
//----------------------//

ll mod_pow(ll x, ll n, ll mod) {
	if (n == 0) return 1;
	ll res = mod_pow(x * x % mod, n / 2, mod);
	if (n & 1) res = res * x % mod;
	return res;
}

vector<ll> fact, inv;
void fact_inv(int n, ll mod) {
	fact.resize(n + 1);
	inv.resize(n + 1);
	
	fact[0] = 1;
	FOR(i, 1, n + 1) fact[i] = fact[i - 1] * i % mod;
	inv[n] = mod_pow(fact[n], mod - 2, mod);
	for (int i = n; i > 0; i--) inv[i - 1] = inv[i] * i % mod;
}

ll ncr(ll n, ll r, ll mod = MOD) {
	if (n < r || r < 0 || n < 0) return 0;
	return fact[n] * inv[r] % mod * inv[n - r] % mod;
}

int N, K;
int atk[112345], def[112345];
int sum[3003][3003];

int getSum(int y1, int x1, int y2, int x2) {
	return sum[y2][x2] - sum[y1 - 1][x2] - sum[y2][x1 - 1] + sum[y1 - 1][x1 - 1];
}

ll solve(int diff, bool f) {
	ll res = 0;
	FOR(i, 1, 3003 - diff) {
		FOR(j, 1, 3003 - diff) {
			int cnt = getSum(i, j, i + diff, j + diff);
			if (!f) {
				if (cnt >= K) return true;
				continue;
			}
			
			int u = getSum(i, j, i, j + diff);
			int l = getSum(i, j, i + diff, j);
			
			ll now = ncr(cnt, K);
			now += MOD - ncr(cnt - u, K);
			now += MOD - ncr(cnt - l, K);
			now += ncr(cnt - u - l, K);
			
			res = (res + now) % MOD;
		}
	}
	
	return res;
}

int main() {
	cin >> N >> K;
	REP(i, N) {
		scanf("%d %d", atk + i, def + i);
		atk[i]++; def[i]++;
		
		assert(atk[i] <= 3001 && def[i] <= 3001);
	}
	
	REP(i, N) sum[atk[i]][def[i]]++;
	REP(i, 3003) REP(j, 3002) sum[i][j + 1] += sum[i][j];
	REP(i, 3002) REP(j, 3003) sum[i + 1][j] += sum[i][j];
	
	fact_inv(N, MOD);
	
	int l = -1, r = 3000;
	while (r - l > 1) {
		int m = (l + r) / 2;
		if (solve(m, false)) r = m;
		else l = m;
	}
	
	cout << r << endl;
	cout << solve(r, true) << endl;
	
	return 0;
}

Submission Info

Submission Time
Task D - アットコーダーモンスターズ
User tkmst201
Language C++14 (GCC 5.4.1)
Score 100
Code Size 2436 Byte
Status AC
Exec Time 255 ms
Memory 37888 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:79:35: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", atk + i, def + i);
                                   ^

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 10 / 10 90 / 90
Status
AC × 4
AC × 13
AC × 41
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 122 ms 35456 KB
subtask0_sample_02.txt AC 177 ms 35456 KB
subtask0_sample_03.txt AC 106 ms 35456 KB
subtask0_sample_04.txt AC 255 ms 35456 KB
subtask1_random01.txt AC 154 ms 35456 KB
subtask1_random02.txt AC 106 ms 35456 KB
subtask1_random03.txt AC 122 ms 35456 KB
subtask1_random04.txt AC 122 ms 35456 KB
subtask1_random05.txt AC 122 ms 35456 KB
subtask1_random06.txt AC 153 ms 35456 KB
subtask1_random07.txt AC 106 ms 35456 KB
subtask1_random08.txt AC 106 ms 35456 KB
subtask1_random09.txt AC 138 ms 35456 KB
subtask1_random10.txt AC 122 ms 35456 KB
subtask2_random01.txt AC 147 ms 37888 KB
subtask2_random02.txt AC 54 ms 37888 KB
subtask2_random03.txt AC 50 ms 37888 KB
subtask2_random04.txt AC 54 ms 37888 KB
subtask2_random05.txt AC 53 ms 37888 KB
subtask2_random06.txt AC 74 ms 37888 KB
subtask2_random07.txt AC 47 ms 37888 KB
subtask2_random08.txt AC 100 ms 37888 KB
subtask2_random09.txt AC 46 ms 37888 KB
subtask2_random10.txt AC 68 ms 37888 KB
subtask2_random11.txt AC 187 ms 37888 KB
subtask2_random12.txt AC 215 ms 37888 KB
subtask2_random13.txt AC 158 ms 37888 KB
subtask2_random14.txt AC 210 ms 37888 KB
subtask2_random15.txt AC 183 ms 37888 KB
subtask2_random16.txt AC 170 ms 37888 KB
subtask2_random17.txt AC 184 ms 37888 KB
subtask2_random18.txt AC 186 ms 37888 KB
subtask2_random19.txt AC 169 ms 37888 KB
subtask2_random20.txt AC 201 ms 37888 KB
subtask2_special01.txt AC 46 ms 37888 KB
subtask2_special02.txt AC 63 ms 37888 KB
subtask2_special03.txt AC 126 ms 37888 KB
subtask2_special04.txt AC 123 ms 37888 KB
subtask2_special05.txt AC 123 ms 37888 KB
subtask2_special06.txt AC 139 ms 37888 KB
subtask2_special07.txt AC 139 ms 37888 KB