Submission #2370003


Source Code Expand

#include <bits/stdc++.h>
using namespace std;

constexpr int mod = 1e9 + 7;

// int64_t dp[334][334][334];
vector<vector<int64_t>> dp(334, vector<int64_t>(334, 0));

int main() {
  int n, m;
  cin >> n >> m;

  dp[n - 1][1] = 1;
  for (int i = 0; i < m; ++i) {
    vector<vector<int64_t>> dp2(334, vector<int64_t>(334, 0));
    for (int j = 0; j < n; ++j) {
      for (int k = 1; k <= n; ++k) {
        (dp2[j][n - j] += k * dp[j][k] % mod) %= mod;
        if (j) (dp2[j - 1][k] += j * dp[j][k] % mod) %= mod;
        (dp2[j][k] += (n - j - k) * dp[j][k]) %= mod;
      }
    }
    dp = dp2;
  }

  cout << dp[0][n] << endl;
}

Submission Info

Submission Time
Task F - Road of the King
User Luzhiled
Language C++14 (GCC 5.4.1)
Score 1000
Code Size 654 Byte
Status AC
Exec Time 339 ms
Memory 2072 KB

Judge Result

Set Name sample all
Score / Max Score 0 / 0 1000 / 1000
Status
AC × 3
AC × 16
Set Name Test Cases
sample sample-01.txt, sample-02.txt, sample-03.txt
all sample-01.txt, sample-02.txt, sample-03.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, sample-01.txt, sample-02.txt, sample-03.txt
Case Name Status Exec Time Memory
01-01.txt AC 2 ms 2048 KB
01-02.txt AC 2 ms 2060 KB
01-03.txt AC 100 ms 2072 KB
01-04.txt AC 3 ms 2048 KB
01-05.txt AC 99 ms 2072 KB
01-06.txt AC 123 ms 2068 KB
01-07.txt AC 322 ms 2072 KB
01-08.txt AC 335 ms 2072 KB
01-09.txt AC 337 ms 2072 KB
01-10.txt AC 339 ms 2072 KB
sample-01.txt AC 3 ms 2072 KB
sample-02.txt AC 160 ms 2072 KB
sample-03.txt AC 171 ms 2072 KB