oj.uz

Submission #82347

# Submission time Handle Problem Language Result Execution time Memory
82347 2018-10-30T08:12:43 Z MrTEK Tents (JOI18_tents) C++14
48 / 100
 238 ms 223976 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;
typedef pair<int,int> ii;

const int N = 3e2 + 5;
const int mod = 1e9 + 7;

int n,m,ans,fac[N],inv[N],dp[N][N][N],dp2[N][N],pw[N];

inline int mul(int x,int y) {
  return (ll) x * y % mod;
}

inline int add(int x,int y) {
  return (x + y) % mod;
}

int fast_pow(int x,int y) {
  if (y == 0)
    return 1;
  int res = fast_pow(x,y / 2);
  res = mul(res,res);
  if(y & 1)
    res = mul(res,x);
  return res;
}

inline int comb(int n,int r) {
  return mul(fac[n],mul(inv[n - r],inv[r]));
}


int g(int x,int y) {
  int &res = dp2[x][y];
  if (x == 0 || y == 0)
    return 1;
  if (res != -1)
    return res;
  res = g(x,y - 1);
  if (x >= 1)
    res = add(res,mul(x * 2,g(x - 1,y - 1)));
  if (x >= 2)
    res = add(res,mul(x * (x - 1) / 2,g(x - 2,y - 1)));
  return res;
}

int f(int t,int x,int y) {
  int &res = dp[t][x][y];
  if (x == 0)
    return res = g(n - t,y);
  if (res != -1)
    return res;
  res = 0;
  if (y >= 2)
    res = add(res,mul(y * (y - 1) / 2,f(t,x - 1,y - 2)));
  if (y >= 1)
    res = add(res,mul(2 * y,f(t,x - 1,y - 1)));
  return res;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  cin >> n >> m;
  pw[0] = inv[0] = fac[0] = 1;
  for (int i = 1 ; i <= max(n,m) ; i++) {
    fac[i] = mul(fac[i - 1],i);
    pw[i] = mul(pw[i - 1],2);
    inv[i] = fast_pow(fac[i],mod - 2);
  }
  memset(dp,-1,sizeof dp);
  memset(dp2,-1,sizeof dp2);
  for (int i = 0 ; i <= n ; i++)
    ans = add(ans,mul(comb(n,i),f(i,i,m)));
  cout << ans - 1 << endl;
}

Subtask #1
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 111864 KB Output is correct
2 Correct 95 ms 112076 KB Output is correct
3 Correct 92 ms 112208 KB Output is correct
4 Correct 93 ms 112208 KB Output is correct
5 Correct 95 ms 112208 KB Output is correct
6 Correct 109 ms 112208 KB Output is correct
7 Correct 98 ms 112208 KB Output is correct
8 Correct 100 ms 112208 KB Output is correct
9 Correct 93 ms 112208 KB Output is correct
10 Correct 126 ms 112208 KB Output is correct
11 Correct 94 ms 112332 KB Output is correct
12 Correct 233 ms 112364 KB Output is correct

Subtask #2
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 111864 KB Output is correct
2 Correct 95 ms 112076 KB Output is correct
3 Correct 92 ms 112208 KB Output is correct
4 Correct 93 ms 112208 KB Output is correct
5 Correct 95 ms 112208 KB Output is correct
6 Correct 109 ms 112208 KB Output is correct
7 Correct 98 ms 112208 KB Output is correct
8 Correct 100 ms 112208 KB Output is correct
9 Correct 93 ms 112208 KB Output is correct
10 Correct 126 ms 112208 KB Output is correct
11 Correct 94 ms 112332 KB Output is correct
12 Correct 233 ms 112364 KB Output is correct
13 Runtime error 238 ms 223976 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Halted 0 ms 0 KB -