# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
20421 | tlwpdus (#35) | 복불복 (OJUZ11_luck) | C++98 | 449 ms | 3164 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// k==1
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<math.h>
#include<queue>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
ll res = 0;
int n, k;
int a[110];
int b[110];
ll po[200][200];
ll dap[110];
ll inv[110];
ll tmp[110];
void calc(const vector<ll> &vec) {
int i, j;
for (i=1;i<=vec.size();i++) {
for (j=0;j<vec.size();j++) {
tmp[i] += po[vec[j]][i];
tmp[i] %= MOD;
}
}
dap[0] = 1;
for (i=1;i<=vec.size();i++) {
dap[i] = 0;
for (j=1;j<=i;j++) {
ll st = ((j-1)%2)?(-1):1;
dap[i] += (st*dap[i-j]*tmp[j])%MOD;
dap[i] %= MOD;
}
dap[i] *= inv[i];
dap[i] = ((dap[i]%MOD)+MOD)%MOD;
}
}
ll popo(ll a, ll n) {
if (n==0) return 1;
ll val = popo(a,n/2);
if (n%2) return (((val*val)%MOD)*a)%MOD;
return (val*val)%MOD;
}
void pre() {
int i;
for (i=1;i<110;i++) inv[i] = popo(i,MOD-2);
}
ll dyn[2010][110];
int pp[20];
int arr[20];
int main() {
int i, j, l;
scanf("%d%d",&n,&k);
for (i=0;i<n;i++) scanf("%d",&a[i]);
for (i=0;i<n;i++) scanf("%d",&b[i]);
sort(a,a+n); sort(b,b+n);
if (k==1) {
for (i=0;i<n;i++) {
int v = a[n-1]+b[i];
ll tres = 1;
for (j=n-2;j>=0;j--) {
int cnt = 0;
for (l=0;l<n;l++) {
if (l==i) continue;
if (a[j]+b[l]>v) break;
cnt++;
}
if (cnt<=n-2-j) {
tres = 0;
break;
}
tres *= cnt-(n-2-j);
tres %= MOD;
}
res += tres;
res %= MOD;
}
printf("%lld\n",res);
}
else if (n<=10) {
for (i=0;i<n;i++) pp[i] = i;
do {
bool flag = true;
for (i=0;i<n;i++) arr[i] = a[i]+b[pp[i]];
for (i=n-k;i<n;i++) {
int cnt = 1;
for (j=0;j<n;j++) {
if (arr[i]<arr[j])cnt++;
}
if (cnt>k) flag = false;
}
if (flag) res++;
}while(next_permutation(pp,pp+n));
printf("%lld\n",res%MOD);
}
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |