oj.uz

Submission #259289

# Submission time Handle Problem Language Result Execution time Memory
259289 2020-08-07T13:51:34 Z Bruteforceman Ruins 3 (JOI20_ruins3) C++11
58 / 100
 6000 ms 23928 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 + 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 20 ms 23296 KB Output is correct
2 Correct 47 ms 23288 KB Output is correct
3 Correct 49 ms 23288 KB Output is correct
4 Correct 35 ms 23288 KB Output is correct
5 Correct 47 ms 23288 KB Output is correct
6 Correct 47 ms 23288 KB Output is correct
7 Correct 49 ms 23292 KB Output is correct
8 Correct 51 ms 23292 KB Output is correct
9 Correct 49 ms 23416 KB Output is correct
10 Correct 49 ms 23288 KB Output is correct

Subtask #2
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23296 KB Output is correct
2 Correct 47 ms 23288 KB Output is correct
3 Correct 49 ms 23288 KB Output is correct
4 Correct 35 ms 23288 KB Output is correct
5 Correct 47 ms 23288 KB Output is correct
6 Correct 47 ms 23288 KB Output is correct
7 Correct 49 ms 23292 KB Output is correct
8 Correct 51 ms 23292 KB Output is correct
9 Correct 49 ms 23416 KB Output is correct
10 Correct 49 ms 23288 KB Output is correct
11 Correct 351 ms 23756 KB Output is correct
12 Correct 328 ms 23800 KB Output is correct
13 Correct 336 ms 23928 KB Output is correct
14 Correct 368 ms 23756 KB Output is correct
15 Correct 319 ms 23800 KB Output is correct
16 Correct 357 ms 23800 KB Output is correct
17 Correct 363 ms 23800 KB Output is correct
18 Correct 350 ms 23928 KB Output is correct
19 Correct 368 ms 23800 KB Output is correct
20 Correct 353 ms 23804 KB Output is correct

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23296 KB Output is correct
2 Correct 47 ms 23288 KB Output is correct
3 Correct 49 ms 23288 KB Output is correct
4 Correct 35 ms 23288 KB Output is correct
5 Correct 47 ms 23288 KB Output is correct
6 Correct 47 ms 23288 KB Output is correct
7 Correct 49 ms 23292 KB Output is correct
8 Correct 51 ms 23292 KB Output is correct
9 Correct 49 ms 23416 KB Output is correct
10 Correct 49 ms 23288 KB Output is correct
11 Correct 351 ms 23756 KB Output is correct
12 Correct 328 ms 23800 KB Output is correct
13 Correct 336 ms 23928 KB Output is correct
14 Correct 368 ms 23756 KB Output is correct
15 Correct 319 ms 23800 KB Output is correct
16 Correct 357 ms 23800 KB Output is correct
17 Correct 363 ms 23800 KB Output is correct
18 Correct 350 ms 23928 KB Output is correct
19 Correct 368 ms 23800 KB Output is correct
20 Correct 353 ms 23804 KB Output is correct
21 Execution timed out 6060 ms 21556 KB Time limit exceeded
22 Halted 0 ms 0 KB -