답안 #528847

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
528847	2022-02-21T15:10:49 Z	Leonardo_Paes	Asceticism (JOI18_asceticism)	C++17	49 / 100	44 ms	72220 KB

asceticism

#include<bits/stdc++.h>
using namespace std;
/*
	Numero de permutacoes de tamanho n com k-1 descidas 
	n = 3, k = 2:
	1) 1 3 2 [1, 3], [2]
	2) 2 1 3 [2], [1, 3]
	3) 2 3 1 [2, 3], [1]
	4) 3 1 2 [3], [1, 2]
*/
typedef long long ll;
const int maxn = 3010, mod = 1e9 + 7;
int dp[maxn][maxn];

int solve(int n, int k){
	if(n == 1) return k == 1; 
	if(dp[n][k] != -1) return dp[n][k];
	ll tot = 1LL * solve(n-1, k) * k + 1LL * solve(n-1, k-1) * (n - k + 1);
	tot %= mod;
	return dp[n][k] = tot;
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	int n, k;
	cin >> n >> k;
	memset(dp, -1, sizeof dp);
	cout << solve(n, k);
	return 0;
}

Subtask #1

4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	18 ms	35716 KB	Output is correct
2	Correct	19 ms	35664 KB	Output is correct
3	Correct	15 ms	35660 KB	Output is correct
4	Correct	15 ms	35784 KB	Output is correct
5	Correct	15 ms	35736 KB	Output is correct
6	Correct	16 ms	35672 KB	Output is correct
7	Correct	15 ms	35652 KB	Output is correct
8	Correct	16 ms	35772 KB	Output is correct
9	Correct	15 ms	35660 KB	Output is correct
10	Correct	14 ms	35772 KB	Output is correct

Subtask #2

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	18 ms	35716 KB	Output is correct
2	Correct	19 ms	35664 KB	Output is correct
3	Correct	15 ms	35660 KB	Output is correct
4	Correct	15 ms	35784 KB	Output is correct
5	Correct	15 ms	35736 KB	Output is correct
6	Correct	16 ms	35672 KB	Output is correct
7	Correct	15 ms	35652 KB	Output is correct
8	Correct	16 ms	35772 KB	Output is correct
9	Correct	15 ms	35660 KB	Output is correct
10	Correct	14 ms	35772 KB	Output is correct
11	Correct	14 ms	35720 KB	Output is correct
12	Correct	21 ms	35772 KB	Output is correct
13	Correct	19 ms	35788 KB	Output is correct
14	Correct	15 ms	35788 KB	Output is correct
15	Correct	15 ms	35776 KB	Output is correct
16	Correct	16 ms	35660 KB	Output is correct
17	Correct	18 ms	35772 KB	Output is correct
18	Correct	16 ms	35700 KB	Output is correct
19	Correct	14 ms	35660 KB	Output is correct
20	Correct	16 ms	35660 KB	Output is correct

Subtask #3

25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	18 ms	35716 KB	Output is correct
2	Correct	19 ms	35664 KB	Output is correct
3	Correct	15 ms	35660 KB	Output is correct
4	Correct	15 ms	35784 KB	Output is correct
5	Correct	15 ms	35736 KB	Output is correct
6	Correct	16 ms	35672 KB	Output is correct
7	Correct	15 ms	35652 KB	Output is correct
8	Correct	16 ms	35772 KB	Output is correct
9	Correct	15 ms	35660 KB	Output is correct
10	Correct	14 ms	35772 KB	Output is correct
11	Correct	14 ms	35720 KB	Output is correct
12	Correct	21 ms	35772 KB	Output is correct
13	Correct	19 ms	35788 KB	Output is correct
14	Correct	15 ms	35788 KB	Output is correct
15	Correct	15 ms	35776 KB	Output is correct
16	Correct	16 ms	35660 KB	Output is correct
17	Correct	18 ms	35772 KB	Output is correct
18	Correct	16 ms	35700 KB	Output is correct
19	Correct	14 ms	35660 KB	Output is correct
20	Correct	16 ms	35660 KB	Output is correct
21	Correct	23 ms	35788 KB	Output is correct
22	Correct	23 ms	35788 KB	Output is correct
23	Correct	23 ms	35776 KB	Output is correct
24	Correct	23 ms	35840 KB	Output is correct
25	Correct	23 ms	35732 KB	Output is correct
26	Correct	25 ms	35788 KB	Output is correct
27	Correct	28 ms	35796 KB	Output is correct
28	Correct	17 ms	35776 KB	Output is correct
29	Correct	18 ms	35684 KB	Output is correct
30	Correct	23 ms	35788 KB	Output is correct

Subtask #4

0 / 51.0

#	결과	실행 시간	메모리	Grader output
1	Correct	18 ms	35716 KB	Output is correct
2	Correct	19 ms	35664 KB	Output is correct
3	Correct	15 ms	35660 KB	Output is correct
4	Correct	15 ms	35784 KB	Output is correct
5	Correct	15 ms	35736 KB	Output is correct
6	Correct	16 ms	35672 KB	Output is correct
7	Correct	15 ms	35652 KB	Output is correct
8	Correct	16 ms	35772 KB	Output is correct
9	Correct	15 ms	35660 KB	Output is correct
10	Correct	14 ms	35772 KB	Output is correct
11	Correct	14 ms	35720 KB	Output is correct
12	Correct	21 ms	35772 KB	Output is correct
13	Correct	19 ms	35788 KB	Output is correct
14	Correct	15 ms	35788 KB	Output is correct
15	Correct	15 ms	35776 KB	Output is correct
16	Correct	16 ms	35660 KB	Output is correct
17	Correct	18 ms	35772 KB	Output is correct
18	Correct	16 ms	35700 KB	Output is correct
19	Correct	14 ms	35660 KB	Output is correct
20	Correct	16 ms	35660 KB	Output is correct
21	Correct	23 ms	35788 KB	Output is correct
22	Correct	23 ms	35788 KB	Output is correct
23	Correct	23 ms	35776 KB	Output is correct
24	Correct	23 ms	35840 KB	Output is correct
25	Correct	23 ms	35732 KB	Output is correct
26	Correct	25 ms	35788 KB	Output is correct
27	Correct	28 ms	35796 KB	Output is correct
28	Correct	17 ms	35776 KB	Output is correct
29	Correct	18 ms	35684 KB	Output is correct
30	Correct	23 ms	35788 KB	Output is correct
31	Runtime error	44 ms	72220 KB	Execution killed with signal 11
32	Halted	0 ms	0 KB	-