oj.uz

답안 #127391

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -