oj.uz

Submission #259291

# Submission time Handle Problem Language Result Execution time Memory
259291 2020-08-07T13:55:09 Z Bruteforceman Ruins 3 (JOI20_ruins3) C++11
58 / 100
 6000 ms 12860 KB 
#include <bits/stdc++.h>
using namespace std;
const int maxn = 605;
const long long mod = 1e9 + 7;
long long 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 * 2][maxn * 2];
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);
  if(mem[cur][bound] != -1) return mem[cur][bound];
  long long ans = (dp(cur + 1, bound) * (n - bound - cur)) % mod;
  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 mem[cur][bound] = 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; i++) {
    memset(mem, -1, sizeof mem);
    var = i;
    ways[i] = calc(var, 0);
  }
  memset(mem, -1, sizeof mem);
  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 2 ms 3200 KB Output is correct
2 Correct 3 ms 3328 KB Output is correct
3 Correct 4 ms 3328 KB Output is correct
4 Correct 3 ms 3200 KB Output is correct
5 Correct 3 ms 3328 KB Output is correct
6 Correct 3 ms 3328 KB Output is correct
7 Correct 3 ms 3328 KB Output is correct
8 Correct 3 ms 3328 KB Output is correct
9 Correct 3 ms 3328 KB Output is correct
10 Correct 3 ms 3328 KB Output is correct

Subtask #2
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3200 KB Output is correct
2 Correct 3 ms 3328 KB Output is correct
3 Correct 4 ms 3328 KB Output is correct
4 Correct 3 ms 3200 KB Output is correct
5 Correct 3 ms 3328 KB Output is correct
6 Correct 3 ms 3328 KB Output is correct
7 Correct 3 ms 3328 KB Output is correct
8 Correct 3 ms 3328 KB Output is correct
9 Correct 3 ms 3328 KB Output is correct
10 Correct 3 ms 3328 KB Output is correct
11 Correct 28 ms 3712 KB Output is correct
12 Correct 28 ms 3772 KB Output is correct
13 Correct 28 ms 3712 KB Output is correct
14 Correct 28 ms 3712 KB Output is correct
15 Correct 27 ms 3712 KB Output is correct
16 Correct 28 ms 3840 KB Output is correct
17 Correct 28 ms 3712 KB Output is correct
18 Correct 31 ms 3712 KB Output is correct
19 Correct 28 ms 3712 KB Output is correct
20 Correct 29 ms 3712 KB Output is correct

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3200 KB Output is correct
2 Correct 3 ms 3328 KB Output is correct
3 Correct 4 ms 3328 KB Output is correct
4 Correct 3 ms 3200 KB Output is correct
5 Correct 3 ms 3328 KB Output is correct
6 Correct 3 ms 3328 KB Output is correct
7 Correct 3 ms 3328 KB Output is correct
8 Correct 3 ms 3328 KB Output is correct
9 Correct 3 ms 3328 KB Output is correct
10 Correct 3 ms 3328 KB Output is correct
11 Correct 28 ms 3712 KB Output is correct
12 Correct 28 ms 3772 KB Output is correct
13 Correct 28 ms 3712 KB Output is correct
14 Correct 28 ms 3712 KB Output is correct
15 Correct 27 ms 3712 KB Output is correct
16 Correct 28 ms 3840 KB Output is correct
17 Correct 28 ms 3712 KB Output is correct
18 Correct 31 ms 3712 KB Output is correct
19 Correct 28 ms 3712 KB Output is correct
20 Correct 29 ms 3712 KB Output is correct
21 Execution timed out 6045 ms 12860 KB Time limit exceeded
22 Halted 0 ms 0 KB -