제출 #640204

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
640204		iee	Zapina (COCI20_zapina)	C++17	110 / 110	521 ms	1792 KiB

zapina

#include <bits/stdc++.h>
using namespace std;
const int N = 355, p = 1e9 + 7;
using ll = long long;
int dp[N][N][2], C[N][N];
int n;
int sit(int man, int seat, bool good) {
  if (man > n) return !seat && good;
  if (dp[man][seat][good] != -1) return dp[man][seat][good];
  int ans = 0;
  for (int i = 0; i <= seat; ++i)
    (ans += 1ll * sit(man + 1, seat - i, good || (i == man)) * C[seat][i] % p) %= p;
  return dp[man][seat][good] = ans;
}
int main() {
  memset(dp, -1, sizeof dp);
  cin >> n;
  for (int i = 0; i <= n; ++i) {
    C[i][0] = 1;
    for (int j = 1; j <= i; ++j)
      C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % p;
  }
  cout << sit(1, n, false);
  return 0;
}

• Subtask 1: 22 / 22
• Subtask 2: 33 / 33
• Subtask 3: 55 / 55