oj.uz

Submission #259299

# Submission time Handle Problem Language Result Execution time Memory
259299 2020-08-07T14:10:13 Z Bruteforceman Ruins 3 (JOI20_ruins3) C++11
58 / 100
 6000 ms 13176 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;
}
long long dp[maxn][maxn];

int main() {
  int n;
  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);
  dp[n][0] = 1;
  for(int cur = n - 1; cur >= 0; cur--) {
    for(int bound = 0; bound <= n; bound++) {
      dp[cur][bound] = (1LL * 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) {
          long long add = ((C[free][bound - i] * ways[bound - i] % mod) * dp[cur + 1][i]) % mod;
          dp[cur][bound] += add;
          dp[cur][bound] %= mod;
        }
      }
    }
  } 
  cout << 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 3 ms 3328 KB Output is correct
4 Correct 3 ms 3328 KB Output is correct
5 Correct 3 ms 3328 KB Output is correct
6 Correct 4 ms 3328 KB Output is correct
7 Correct 4 ms 3328 KB Output is correct
8 Correct 4 ms 3328 KB Output is correct
9 Correct 4 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 3 ms 3328 KB Output is correct
4 Correct 3 ms 3328 KB Output is correct
5 Correct 3 ms 3328 KB Output is correct
6 Correct 4 ms 3328 KB Output is correct
7 Correct 4 ms 3328 KB Output is correct
8 Correct 4 ms 3328 KB Output is correct
9 Correct 4 ms 3328 KB Output is correct
10 Correct 3 ms 3328 KB Output is correct
11 Correct 31 ms 3960 KB Output is correct
12 Correct 29 ms 4096 KB Output is correct
13 Correct 29 ms 4216 KB Output is correct
14 Correct 28 ms 4088 KB Output is correct
15 Correct 28 ms 3960 KB Output is correct
16 Correct 29 ms 3960 KB Output is correct
17 Correct 27 ms 3960 KB Output is correct
18 Correct 28 ms 3968 KB Output is correct
19 Correct 28 ms 3960 KB Output is correct
20 Correct 28 ms 3960 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 3 ms 3328 KB Output is correct
4 Correct 3 ms 3328 KB Output is correct
5 Correct 3 ms 3328 KB Output is correct
6 Correct 4 ms 3328 KB Output is correct
7 Correct 4 ms 3328 KB Output is correct
8 Correct 4 ms 3328 KB Output is correct
9 Correct 4 ms 3328 KB Output is correct
10 Correct 3 ms 3328 KB Output is correct
11 Correct 31 ms 3960 KB Output is correct
12 Correct 29 ms 4096 KB Output is correct
13 Correct 29 ms 4216 KB Output is correct
14 Correct 28 ms 4088 KB Output is correct
15 Correct 28 ms 3960 KB Output is correct
16 Correct 29 ms 3960 KB Output is correct
17 Correct 27 ms 3960 KB Output is correct
18 Correct 28 ms 3968 KB Output is correct
19 Correct 28 ms 3960 KB Output is correct
20 Correct 28 ms 3960 KB Output is correct
21 Execution timed out 6024 ms 13176 KB Time limit exceeded
22 Halted 0 ms 0 KB -