Submission #993143


Source Code Expand

#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <bitset>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <queue>

#define mp make_pair
#define pb push_back


typedef long long ll;
typedef long double ld;

using namespace std;
const ll MOD = 1e9 + 7;

ll dp[310][310];
ll dp2[310][310];

void add(ll &a, ll b) {
	a += b;
	a %= MOD;
}
int n, m;

int main() {
	cin >> n >> m;
	dp[1][1] = 1;
	for (int i = 1; i <= m; ++i) {
		for (int j = 1; j <= n; ++j)
			for (int k = 1; k <= j; ++k)
				dp2[j][k] = 0;
		for (int j = 1; j <= n; ++j)
			for (int k = 1; k <= j; ++k) {
				add(dp2[j + 1][k], dp[j][k] * (n - j));
				add(dp2[j][j], dp[j][k] * k);
				add(dp2[j][k], dp[j][k] * (j - k));
			}
		for (int j = 1; j <= n; ++j)
			for (int k = 1; k <= j; ++k)
				dp[j][k] = dp2[j][k];
	}
	cout << dp[n][n] << "\n";
	return 0;
}


Submission Info

Submission Time
Task F - Road of the King
User LHiC
Language C++14 (GCC 5.4.1)
Score 1000
Code Size 1001 Byte
Status AC
Exec Time 103 ms
Memory 1792 KB

Judge Result

Set Name sample all
Score / Max Score 0 / 0 1000 / 1000
Status
AC × 3
AC × 13
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
Case Name Status Exec Time Memory
01-01.txt AC 3 ms 256 KB
01-02.txt AC 3 ms 256 KB
01-03.txt AC 3 ms 256 KB
01-04.txt AC 5 ms 1664 KB
01-05.txt AC 3 ms 256 KB
01-06.txt AC 12 ms 640 KB
01-07.txt AC 96 ms 1664 KB
01-08.txt AC 102 ms 1664 KB
01-09.txt AC 102 ms 1664 KB
01-10.txt AC 103 ms 1792 KB
sample-01.txt AC 3 ms 256 KB
sample-02.txt AC 29 ms 1024 KB
sample-03.txt AC 54 ms 1664 KB