CODE FESTIVAL 2016 Final

Submission #11224676

Source codeソースコード

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>
#include <stdio.h>
#include <iomanip>
#include <limits>
#include <list>
#include <string>
#include <queue>
#include <deque>
#include <tuple>
#include <map>
#include <sstream>
using namespace std;
#define MOD (long long int)(1e9+7)
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define FOR(i,a,b) for(int i=a; i<(int)(b); i++)
#define ALL(x) (x).begin(),(x).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define SORT(c) sort(ALL(x))
#define CLR(a) memset((a), 0 ,sizeof(a))
#define PB push_back
#define MP make_pair
#define SP << " " <<
const int INF = 1001001001;
const ll LINF = 100100100100100100;
const double EPS = 1e-10;
const long double PI  = acos(-1.0L);
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
#define chmax(a,b) a = (((a)<(b))?(b):(a))
#define chmin(a,b) a = (((a)>(b))?(b):(a))

__attribute__((constructor))
void initial(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
}

signed main(){
	int n,m; cin>>n>>m;
	ll dp[m+5][n+5][n+5]; CLR(dp);
	dp[0][1][1] = 1;
	rep(i,m+1){
		rep(j,n+1){
			rep(k,n+1){
				dp[i+1][j+1][k] += dp[i][j][k]*(n-j)%MOD; // 新しい街に行く
				dp[i+1][j+1][k] %= MOD;
				dp[i+1][j][k] += dp[i][j][k]*(j-k)%MOD; // 強連結要素につなげない
				dp[i+1][j][k] %= MOD;
				dp[i+1][j][j] += dp[i][j][k]*k%MOD; // 強連結化
				dp[i+1][j][j] %= MOD;
			}
		}
	}
	cout << dp[m][n][n] << endl;

  return 0;
}

Submission

Task問題 F - Road of the King
User nameユーザ名 m_9719
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 1000
Source lengthソースコード長 1797 Byte
File nameファイル名
Exec time実行時間 317 ms
Memory usageメモリ使用量 221952 KB

Test case

Set

Set name Score得点 / Max score Cases
sample - sample-01.txt,sample-02.txt,sample-03.txt
all 1000 / 1000 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
01-01.txt AC 1 ms 256 KB
01-02.txt AC 1 ms 256 KB
01-03.txt AC 1 ms 384 KB
01-04.txt AC 4 ms 4608 KB
01-05.txt AC 2 ms 768 KB
01-06.txt AC 30 ms 21376 KB
01-07.txt AC 296 ms 206976 KB
01-08.txt AC 314 ms 219008 KB
01-09.txt AC 316 ms 220416 KB
01-10.txt AC 317 ms 221952 KB
sample-01.txt AC 1 ms 256 KB
sample-02.txt AC 82 ms 57472 KB
sample-03.txt AC 160 ms 112896 KB