oj.uz

Submission #259290

# Submission time Handle Problem Language Result Execution time Memory
259290 2020-08-07T13:52:26 Z Bruteforceman Ruins 3 (JOI20_ruins3) C++11
58 / 100
 6000 ms 23804 KB 
#include <bits/stdc++.h>
using namespace std;
const int maxn = 605 * 2;
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][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 fn[maxn][maxn];
long long dp(int cur, int bound) {
  if(cur == n) return (bound == 0);
  if(fn[cur][bound] != -1) return fn[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 fn[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(fn, -1, sizeof fn);
  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 12 ms 23296 KB Output is correct
2 Correct 31 ms 23296 KB Output is correct
3 Correct 27 ms 23424 KB Output is correct
4 Correct 28 ms 23296 KB Output is correct
5 Correct 28 ms 23288 KB Output is correct
6 Correct 29 ms 23288 KB Output is correct
7 Correct 28 ms 23288 KB Output is correct
8 Correct 33 ms 23288 KB Output is correct
9 Correct 28 ms 23288 KB Output is correct
10 Correct 29 ms 23288 KB Output is correct

Subtask #2
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23296 KB Output is correct
2 Correct 31 ms 23296 KB Output is correct
3 Correct 27 ms 23424 KB Output is correct
4 Correct 28 ms 23296 KB Output is correct
5 Correct 28 ms 23288 KB Output is correct
6 Correct 29 ms 23288 KB Output is correct
7 Correct 28 ms 23288 KB Output is correct
8 Correct 33 ms 23288 KB Output is correct
9 Correct 28 ms 23288 KB Output is correct
10 Correct 29 ms 23288 KB Output is correct
11 Correct 113 ms 23800 KB Output is correct
12 Correct 108 ms 23800 KB Output is correct
13 Correct 112 ms 23804 KB Output is correct
14 Correct 108 ms 23800 KB Output is correct
15 Correct 129 ms 23804 KB Output is correct
16 Correct 149 ms 23800 KB Output is correct
17 Correct 129 ms 23800 KB Output is correct
18 Correct 129 ms 23756 KB Output is correct
19 Correct 122 ms 23752 KB Output is correct
20 Correct 132 ms 23800 KB Output is correct

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23296 KB Output is correct
2 Correct 31 ms 23296 KB Output is correct
3 Correct 27 ms 23424 KB Output is correct
4 Correct 28 ms 23296 KB Output is correct
5 Correct 28 ms 23288 KB Output is correct
6 Correct 29 ms 23288 KB Output is correct
7 Correct 28 ms 23288 KB Output is correct
8 Correct 33 ms 23288 KB Output is correct
9 Correct 28 ms 23288 KB Output is correct
10 Correct 29 ms 23288 KB Output is correct
11 Correct 113 ms 23800 KB Output is correct
12 Correct 108 ms 23800 KB Output is correct
13 Correct 112 ms 23804 KB Output is correct
14 Correct 108 ms 23800 KB Output is correct
15 Correct 129 ms 23804 KB Output is correct
16 Correct 149 ms 23800 KB Output is correct
17 Correct 129 ms 23800 KB Output is correct
18 Correct 129 ms 23756 KB Output is correct
19 Correct 122 ms 23752 KB Output is correct
20 Correct 132 ms 23800 KB Output is correct
21 Execution timed out 6082 ms 21368 KB Time limit exceeded
22 Halted 0 ms 0 KB -