Submission #20339

#	Time	Username	Problem	Language	Result	Execution time	Memory
20339		admin	복불복 (OJUZ11_luck)	C++11	100 / 100	174 ms	2292 KiB

luck

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <deque>
#include <utility>
#include <bitset>
#include <limits.h>
#include <time.h>
#include <functional>
#include <numeric>
 
using namespace std;
typedef long long ll;
typedef unsigned long long llu;
typedef double lf;
typedef unsigned int uint;
typedef long double llf;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
 
#define debug(format, ...) printf(format, __VA_ARGS__);
 
const int N_ = 350;
const int MOD = (int)1e9 + 7;
 
int N, K;
int A[N_], B[N_];
 
int comb[N_][N_];
int fac[N_];
 
struct mint {
	ll val;
	mint() { val = 0; }
	mint(ll val): val(val % MOD) { val = 0; }
	~mint() { }
	ll& operator*()	{ return val;}
	mint operator+ (mint t) { return val + t.val; }
	mint operator- (mint t) { return val - t.val + MOD; }
	mint operator* (mint t) { return val * t.val; }
	mint operator+= (mint t) { return *this = (val + t.val); }
	mint operator-= (mint t) { return *this = (val - t.val); }
};
 
int bound[N_];
 
mint ta[N_][N_];
mint tb[N_][N_];
 
int ha[N_];
 
ll nat (ll x) {
	return (x < 0) ? 0 : x;
}
 
mint count_cases (int L, int R) {
	mint ret = 0;
 
	// bound 구하기
	for(int i = K, cur = 1; i > 0; i--) {
		while(cur <= N && B[cur] <= L - A[i]) cur += 1;
		if(cur == 1) return 0;
		bound[i] = cur - 1;
	}
	for(int i = K+1, cur = N; i <= N; i++) {
		while(cur > 0 && B[cur] >= R - A[i]) cur -= 1;
		if(cur == N) return 0;
		bound[i] = cur + 1;
	}
 
 
	// prep
	for(int j = 1; j <= N; j++) {
		ha[j] = 0;
		for(int i = 1; i <= K; i++) if(j <= bound[i]) ha[j] += 1;
	}
 
	for(int k = 0; k <= K; k++) {
		// ta
		fill(ta[k], ta[k] + N + 2, 0);
		if(k == 0) {
			for(int j = 1; j <= N+1; j++) ta[k][j] = 1;
		}else {
			for(int j = N+1; j >= bound[K+1]; j--) {
				ta[k][j] = ta[k][j+1];
				if(ha[j] >= k) ta[k][j] += ta[k-1][j+1] * nat(ha[j] - k + 1);
			}
		}
 
		tb[K][K-k] = ta[k][bound[K+1]] * fac[K-k];
	}
 
	for(int i = K+1; i <= N; i++) {
		int d = (i == K+1) ? 0 : (bound[i-1] - bound[i]);
		for(int c = 0; c <= K; c++) {
			tb[i][c] = 0;
			for(int z = 0; z <= d && c+z <= K; z++)
				tb[i][c] += tb[i-1][c+z] * comb[d][z] * nat((N - bound[i] + 1) - (i-1-c));
		}
	}
 
	for(int z = 0; z <= bound[N]-1 && z <= K; z++)
		ret += tb[N][z] * comb[bound[N]-1][z];
 
	return ret;
}
 
/* 서브태스크 */
// 1. n <= 8 (n!) -O
// 2. n <= 100, k = 1 (n) -X
// 3. n <= 15 (n^3 2^n)
// 4. k <= 8 (n^3 k^2)
// 5. n <= 100 (n^3 k) -O
 
int main() {
	scanf("%d%d", &N, &K);
	for(int i = 1; i <= N; i++) scanf("%d", A+i);
	for(int i = 1; i <= N; i++) scanf("%d", B+i);
	sort(A+1, A+N+1, greater<int>());
	sort(B+1, B+N+1, greater<int>());
	for(int i = N; i > 0; i--) A[i] = A[1] - A[i], B[i] = B[1] - B[i];
 
	// nCr
	comb[0][0] = 1;
	for(int i = 1; i <= N; i++) {
		comb[i][0] = comb[i][i] = 1;
		for(int j = 1; j < i; j++) comb[i][j] = (comb[i-1][j] + comb[i-1][j-1]) % MOD;	
	}
 
 
	fac[0] = 1;
	for(int i = 1; i <= N; i++)
		fac[i] = ((ll)fac[i-1] * i) % MOD;
 
	if(N == K)
		return 0 & printf("%d\n", fac[N]);
 
	mint ans = 0;
	for(int X = A[K] + B[1]; X <= A[N] + B[N]; X++) {
		ans += count_cases(X, X) - count_cases(X-1, X);
	}
 
	printf("%lld\n", *ans);
 
	return 0;
}

Compilation message (stderr)

luck.cpp: In function 'int main()':
luck.cpp:127:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &K);
                       ^
luck.cpp:128:46: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1; i <= N; i++) scanf("%d", A+i);
                                              ^
luck.cpp:129:46: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1; i <= N; i++) scanf("%d", B+i);
                                              ^

• Subtask 1: 9 / 9
• Subtask 2: 13 / 13
• Subtask 3: 25 / 25
• Subtask 4: 26 / 26
• Subtask 5: 27 / 27