Submission #474620

#	Time	Username	Problem	Language	Result	Execution time	Memory
474620		prvocislo	Asceticism (JOI18_asceticism)	C++17	49 / 100	46 ms	24964 KiB

asceticism

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
typedef long long ll;
using namespace std;

const int maxn = 3005, mod = 1e9 + 7;
int dp[maxn][maxn];
int mul(const int& a, const int& b) { return (a * 1ll * b) % (ll)mod; }
void upd(int& a, const int& b) { a = (a + b) % mod; }
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int N, K;
	cin >> N >> K;
	dp[1][1] = 1;
	for (int n = 2; n <= N; n++) for (int k = 1; k <= min(K, n); k++)
	{
		upd(dp[n][k], mul(dp[n - 1][k], k)); // umiestnime ho na koniec jedneho z k usekov
		upd(dp[n][k], mul(dp[n - 1][k - 1], n - k + 1)); //  umiestnime ho inde a vytvorime novy usek
	}
	cout << dp[N][K] << "\n";
	return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 20 / 20
• Subtask 3: 25 / 25
• Subtask 4: 0 / 51