fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define pb push_back
  4. #define int long long
  5. #define ull unsigned long long
  6. #define fi first
  7. #define se second
  8. #define SZ(x) ((int)(x).size())
  9. #define ALL(x) (x).begin(), (x).end()
  10. #define MASK(i) ((1LL)<<(i))
  11. #define GETBIT(x,i) (((x)>>(i))&1)
  12. #define TURNOFF(x,i) ((x)&(~(1<<i)))
  13. #define CNTBIT(x) __builtin_popcount(x)
  14. #define LOG 20
  15. #define MASK(i) ((1LL)<<(i))
  16. #define EL cout << "\n"
  17. #define FU(i, a, b) for(int i=a; i<=b; i++)
  18. #define FD(i, a, b) for(int i=a; i>=b; i--)
  19. #define REP(i, x) for(int i=0; i<x; i++)
  20. #define REPD(i, x) for(int i=x-1; i>=0; i--)
  21. const int MAX = 1e3 + 5;
  22. const int mod = 1e9 + 9;
  23. const int base = 31;
  24. const int INF = 1e9 + 7;
  25. typedef pair<int, int> ii;
  26.  
  27. #define task "team"
  28. void init()
  29. {
  30.     if (fopen(task".inp","r"))
  31.     {
  32.         freopen(task".inp","r",stdin);
  33.         freopen(task".out","w",stdout);
  34.     }
  35.     else if (fopen(task".in", "r"))
  36.     {
  37.        freopen(task".in", "r", stdin);
  38.        freopen(task".out", "w", stdout);
  39.     }
  40. }
  41.  
  42. void fastio()
  43. {
  44.     ios_base::sync_with_stdio(false);
  45.     cin.tie(0);
  46.     cout.tie(0);
  47. }
  48. int dx[]={0,1,0,-1,1,1,-1,-1};
  49. int dy[]={1,0,-1,0,1,-1,1,-1};
  50. template<class X, class Y> bool maximize(X &x, Y y){ if (x < y) {x = y; return true;} return false;};
  51. template<class X, class Y> bool minimize(X &x, Y y){ if (x > y) {x = y; return true;} return false;};
  52. void add(int &x, int y) { x += y; if (x>=mod) x-=mod;}
  53. void sub(int &x, int y) { x -= y; if (x<0) x+=mod;}
  54. int mul(int x, int y) {return 1LL * x * y % mod;}
  55. int calPw(int x, int y)
  56. {
  57.     int ans = 1;
  58.     while(y)
  59.     {
  60.         if (y&1) ans = 1LL * ans * x % mod;
  61.         x = 1LL * x * x % mod;
  62.         y >>= 1;
  63.     }
  64.     return ans;
  65. }
  66. int N, M, K;
  67. int a[MAX], b[MAX], dp[MAX][MAX][12];
  68. void read()
  69. {
  70.    cin >> N >> M >> K;
  71.    FU(i, 1, N) cin >> a[i];
  72.    FU(i, 1, M) cin >> b[i];
  73. }
  74. void sol()
  75. {
  76.    sort(a+1, a+N+1);
  77.    sort(b+1, b+M+1);
  78.    FU(i, 0, N) FU(j, 0, M) dp[i][j][0] = 1;
  79.    FU(i, 1, N) FU(j, 1, M) FU(k, 1, K)
  80.    {
  81.       dp[i][j][k] = (dp[i-1][j][k] + dp[i][j-1][k] - dp[i-1][j-1][k] + mod) % mod;
  82.       if (a[i] > b[j]) add(dp[i][j][k], dp[i-1][j-1][k-1]);
  83.    }
  84.    cout << dp[N][M][K];
  85. }
  86. signed main()
  87. {
  88.     fastio();
  89.     init();
  90.     int TEST = 1;
  91.     //cin >> TEST;
  92.     while(TEST--)
  93.     {
  94.         read();
  95.         sol();
  96.     }
  97. }
  98.  
Success #stdin #stdout 0.01s 5436KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/zbgdQl
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!