Submission #20339

#TimeUsernameProblemLanguageResultExecution timeMemory
20339admin복불복 (OJUZ11_luck)C++11
100 / 100
174 ms2292 KiB
#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);
                                              ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...