Submission #1680677


Source Code Expand

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

const ll p = 1e9+7;

int n, m;
ll dp[305][305];
ll dp1[305][305];

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

	dp[1][0] = 1;
	for (int i = 1; i <= m; ++i) {
		memset(dp1, 0, sizeof(dp1));
		for (int j = 1; j <= i; ++j)
			for (int k = 0; k <= i-j; ++k) {
				if (k == 0) {
					dp1[j][k] = (dp1[j][k] + j*dp[j][k])%p;
					dp1[j][k+1] = (dp1[j][k+1] + (n-j)*dp[j][k])%p;
				} else {
					dp1[j][k] = (dp1[j][k] + k*dp[j][k])%p;
					dp1[j+k][0] = (dp1[j+k][0] + j*dp[j][k])%p;
					dp1[j][k+1] = (dp1[j][k+1] + (n-j-k)*dp[j][k])%p;
				}
			}
		memcpy(dp, dp1, sizeof(dp));
	}

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

Submission Info

Submission Time
Task F - Road of the King
User desert97
Language C++14 (GCC 5.4.1)
Score 1000
Code Size 694 Byte
Status AC
Exec Time 60 ms
Memory 1664 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 1664 KB
01-02.txt AC 2 ms 1664 KB
01-03.txt AC 60 ms 1664 KB
01-04.txt AC 2 ms 1664 KB
01-05.txt AC 60 ms 1664 KB
01-06.txt AC 60 ms 1664 KB
01-07.txt AC 59 ms 1664 KB
01-08.txt AC 60 ms 1664 KB
01-09.txt AC 60 ms 1664 KB
01-10.txt AC 60 ms 1664 KB
sample-01.txt AC 2 ms 1664 KB
sample-02.txt AC 60 ms 1664 KB
sample-03.txt AC 19 ms 1664 KB