Submission #20421

#TimeUsernameProblemLanguageResultExecution timeMemory
20421tlwpdus (#35)복불복 (OJUZ11_luck)C++98
13 / 100
449 ms3164 KiB
// 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)

luck.cpp: In function 'void calc(const std::vector<long long int>&)':
luck.cpp:25:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i=1;i<=vec.size();i++) {
            ^
luck.cpp:26:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (j=0;j<vec.size();j++) {
             ^
luck.cpp:32:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i=1;i<=vec.size();i++) {
            ^
luck.cpp: In function 'int main()':
luck.cpp:62:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&k);
                     ^
luck.cpp:63:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (i=0;i<n;i++) scanf("%d",&a[i]);
                                     ^
luck.cpp:64:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (i=0;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...