oj.uz

Submission #259285

# Submission time Handle Problem Language Result Execution time Memory
259285 2020-08-07T13:46:02 Z Bruteforceman Ruins 3 (JOI20_ruins3) C++11
6 / 100
 6000 ms 12408 KB 
#include <bits/stdc++.h>
using namespace std;
const int maxn = 605 * 2;
const long long mod = 1e9 + 7;
int ways[maxn];
int a[maxn];

long long binpow(long long x, long long y) {
  long long ans = 1;
  long long power = x;
  while(y) {
    if(y & 1) ans = (ans * power) % mod;
    power = (power * power) % mod;
    y >>= 1;
  }
  return ans;
}
long long inv(long long x) {
  return binpow(x % mod, mod - 2);
}
int var;
long long mem[maxn][maxn];
long long C[maxn][maxn];
long long fac[] = {1, 1, 2};

long long calc(int cur, int take) {
  long long ans = 0;
  if(cur == 1) {
    for(int i = 0; i <= 2; i++) {
      if(take + i == var + 1) {
        return (C[take + i][i] * inv(fac[2 - i])) % mod;
      }
    }
    return 0;
  }
  if(mem[cur][take] != -1) return mem[cur][take];
  for(int i = 0; i <= 2; i++) {
    if(take + i <= var - cur + 1) {
      long long add = (calc(cur - 1, take + i) * C[take + i][i]) % mod;
      ans += (add * inv(fac[2 - i])) % mod;
      ans %= mod;
    }
  }
  return mem[cur][take] = ans;
}
int n;
long long dp(int cur, int bound) {
  if(cur == n) return (bound == 0);
  long long ans = dp(cur + 1, bound) * (n - bound - cur);
  for(int i = 0; i < bound; i++) {
    int free = a[cur + 1] - (n - bound + (cur + 1));
    if(free < bound - i) continue;
    ans += ((C[free][bound - i] * 
      ways[bound - i]) % mod) * dp(cur + 1, i);
    ans %= mod;
  }
  return ans;
}

int main() {
  cin >> n;
  for(int i = 1; i <= n; i++) cin >> a[i];
  for(int i = 0; i <= n + n; i++) {
    C[i][0] = 1;
    for(int j = 1; j <= i; j++) {
      C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
    }
  }
  for(int i = 1; i <= n + n; i++) {
    memset(mem, -1, sizeof mem);
    var = i;
    ways[i] = calc(var, 0);
  }
  cout << ((a[n] != n + n) ? 0 : dp(0, n)) << endl;
  return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11776 KB Output is correct
2 Correct 122 ms 11904 KB Output is correct
3 Correct 85 ms 11904 KB Output is correct
4 Correct 30 ms 11904 KB Output is correct
5 Correct 58 ms 11928 KB Output is correct
6 Correct 67 ms 11904 KB Output is correct
7 Correct 41 ms 11904 KB Output is correct
8 Correct 166 ms 12024 KB Output is correct
9 Correct 186 ms 11904 KB Output is correct
10 Correct 165 ms 11904 KB Output is correct

Subtask #2
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11776 KB Output is correct
2 Correct 122 ms 11904 KB Output is correct
3 Correct 85 ms 11904 KB Output is correct
4 Correct 30 ms 11904 KB Output is correct
5 Correct 58 ms 11928 KB Output is correct
6 Correct 67 ms 11904 KB Output is correct
7 Correct 41 ms 11904 KB Output is correct
8 Correct 166 ms 12024 KB Output is correct
9 Correct 186 ms 11904 KB Output is correct
10 Correct 165 ms 11904 KB Output is correct
11 Execution timed out 6065 ms 12408 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11776 KB Output is correct
2 Correct 122 ms 11904 KB Output is correct
3 Correct 85 ms 11904 KB Output is correct
4 Correct 30 ms 11904 KB Output is correct
5 Correct 58 ms 11928 KB Output is correct
6 Correct 67 ms 11904 KB Output is correct
7 Correct 41 ms 11904 KB Output is correct
8 Correct 166 ms 12024 KB Output is correct
9 Correct 186 ms 11904 KB Output is correct
10 Correct 165 ms 11904 KB Output is correct
11 Execution timed out 6065 ms 12408 KB Time limit exceeded
12 Halted 0 ms 0 KB -