oj.uz

Submission #528847

# Submission time Handle Problem Language Result Execution time Memory
528847 2022-02-21T15:10:49 Z Leonardo_Paes Asceticism (JOI18_asceticism) C++17
49 / 100
 44 ms 72220 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -