oj.uz

Submission #127389

# Submission time Handle Problem Language Result Execution time Memory
127389 2019-07-09T10:11:46 Z RockyB Tents (JOI18_tents) C++17
48 / 100
 631 ms 107220 KB 
#include <bits/stdc++.h>

#define rep(a, b, c) for (int a = (b); (b) <= (c); a++)
#define per(a, b, c) for (int a = (b); (b) >= (c); a--)

#define nl '\n'
#define ioi exit(0);

const int mod = (int)1e9 + 7;

using namespace std;

void add(int &x, int y) {
  x += y;
  if (x >= mod) x -= mod;
  if (x < 0) x += mod;
}
int sum(int x, int y) {
  add(x, y);
  return x;
}

int n, m;

int dp[301][301][301];
int calc(int v = 1, int free = m, int must = 0) {
  if (v > n) return 1;
  if (~dp[v][free][must]) return dp[v][free][must];
  int res = calc(v + 1, free, must);
  // put < or > or ^
  if (free > 0) add(res, calc(v + 1, free - 1, must) * 1ll * free * 3 % mod);
  // connect v and ^
  if (must > 0) add(res, calc(v + 1, free, must - 1) * 1ll * must % mod);
  // open v
  if (free > 0) add(res, calc(v + 1, free - 1, must + 1) * 1ll * free % mod);
  // connect > and <
  if (free > 1) add(res, calc(v + 1, free - 2, must) * 1ll * (free * (free - 1) / 2) % mod);
  return dp[v][free][must] = res;
}
int main() {
  #ifdef IOI
    freopen ("in.txt", "r", stdin);
  #endif
  cin >> n >> m;
  memset(dp, -1, sizeof(dp));
  cout << sum(-1, calc()) << nl;
  ioi
}

Subtask #1
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 107000 KB Output is correct
2 Correct 90 ms 107128 KB Output is correct
3 Correct 92 ms 107128 KB Output is correct
4 Correct 91 ms 107016 KB Output is correct
5 Correct 96 ms 107096 KB Output is correct
6 Correct 138 ms 107128 KB Output is correct
7 Correct 107 ms 107008 KB Output is correct
8 Correct 117 ms 107044 KB Output is correct
9 Correct 91 ms 107128 KB Output is correct
10 Correct 235 ms 107128 KB Output is correct
11 Correct 90 ms 107000 KB Output is correct
12 Correct 631 ms 107220 KB Output is correct

Subtask #2
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 107000 KB Output is correct
2 Correct 90 ms 107128 KB Output is correct
3 Correct 92 ms 107128 KB Output is correct
4 Correct 91 ms 107016 KB Output is correct
5 Correct 96 ms 107096 KB Output is correct
6 Correct 138 ms 107128 KB Output is correct
7 Correct 107 ms 107008 KB Output is correct
8 Correct 117 ms 107044 KB Output is correct
9 Correct 91 ms 107128 KB Output is correct
10 Correct 235 ms 107128 KB Output is correct
11 Correct 90 ms 107000 KB Output is correct
12 Correct 631 ms 107220 KB Output is correct
13 Correct 91 ms 107128 KB Output is correct
14 Incorrect 91 ms 107128 KB Output isn't correct
15 Halted 0 ms 0 KB -