oj.uz

Submission #127391

# Submission time Handle Problem Language Result Execution time Memory
127391 2019-07-09T10:12:12 Z RockyB Tents (JOI18_tents) C++17
48 / 100
 624 ms 107128 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];
inline 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 122 ms 107000 KB Output is correct
2 Correct 107 ms 107000 KB Output is correct
3 Correct 91 ms 107000 KB Output is correct
4 Correct 107 ms 107080 KB Output is correct
5 Correct 102 ms 107004 KB Output is correct
6 Correct 143 ms 107000 KB Output is correct
7 Correct 108 ms 107000 KB Output is correct
8 Correct 121 ms 107096 KB Output is correct
9 Correct 91 ms 107016 KB Output is correct
10 Correct 257 ms 107128 KB Output is correct
11 Correct 91 ms 107000 KB Output is correct
12 Correct 624 ms 107108 KB Output is correct

Subtask #2
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 107000 KB Output is correct
2 Correct 107 ms 107000 KB Output is correct
3 Correct 91 ms 107000 KB Output is correct
4 Correct 107 ms 107080 KB Output is correct
5 Correct 102 ms 107004 KB Output is correct
6 Correct 143 ms 107000 KB Output is correct
7 Correct 108 ms 107000 KB Output is correct
8 Correct 121 ms 107096 KB Output is correct
9 Correct 91 ms 107016 KB Output is correct
10 Correct 257 ms 107128 KB Output is correct
11 Correct 91 ms 107000 KB Output is correct
12 Correct 624 ms 107108 KB Output is correct
13 Correct 91 ms 107000 KB Output is correct
14 Incorrect 91 ms 107084 KB Output isn't correct
15 Halted 0 ms 0 KB -