oj.uz

Submission #44863

# Submission time Handle Problem Language Result Execution time Memory
44863 2018-04-08T13:21:32 Z PowerOfNinjaGo Asceticism (JOI18_asceticism) C++17
49 / 100
 84 ms 56064 KB 
//Power Of Ninja Go
#include <bits/stdc++.h>
//#ifdef atom #else #endif
using namespace std;
typedef long long ll; typedef pair<int, int> ii; typedef vector<int> vi; typedef vector< ii > vii;
#define X first
#define Y second
#define pb push_back
const int md = 1e9+7;
void add(int &a, int b)
{
    a += b;
    if(a>= md) a-= md;
}
int mul(int a, int b)
{
    return (1LL*a*b)%md;
}
const int maxn = 3e3+5;
int dp[maxn][maxn];
int main()
{
    int n, k;
    cin >> n >> k;
    dp[1][0] = 1;
    for(int i = 2; i<= n; i++)
    {
        for(int j = 0; j< i; j++)
        {
            dp[i][j] = mul(j+1, dp[i-1][j]);
            add(dp[i][j], mul(i-j, dp[i-1][j-1]));
            //printf("dp[%d][%d] = %d\n", i, j, dp[i][j]);
        }
    }
    cout << dp[n][k-1] << endl;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 428 KB Output is correct
4 Correct 2 ms 428 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 2 ms 520 KB Output is correct
8 Correct 2 ms 592 KB Output is correct
9 Correct 2 ms 592 KB Output is correct
10 Correct 2 ms 720 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 428 KB Output is correct
4 Correct 2 ms 428 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 2 ms 520 KB Output is correct
8 Correct 2 ms 592 KB Output is correct
9 Correct 2 ms 592 KB Output is correct
10 Correct 2 ms 720 KB Output is correct
11 Correct 2 ms 996 KB Output is correct
12 Correct 3 ms 1892 KB Output is correct
13 Correct 3 ms 1892 KB Output is correct
14 Correct 3 ms 1900 KB Output is correct
15 Correct 3 ms 1900 KB Output is correct
16 Correct 3 ms 1916 KB Output is correct
17 Correct 2 ms 1916 KB Output is correct
18 Correct 3 ms 1916 KB Output is correct
19 Correct 2 ms 1916 KB Output is correct
20 Correct 2 ms 1916 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 428 KB Output is correct
4 Correct 2 ms 428 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 2 ms 520 KB Output is correct
8 Correct 2 ms 592 KB Output is correct
9 Correct 2 ms 592 KB Output is correct
10 Correct 2 ms 720 KB Output is correct
11 Correct 2 ms 996 KB Output is correct
12 Correct 3 ms 1892 KB Output is correct
13 Correct 3 ms 1892 KB Output is correct
14 Correct 3 ms 1900 KB Output is correct
15 Correct 3 ms 1900 KB Output is correct
16 Correct 3 ms 1916 KB Output is correct
17 Correct 2 ms 1916 KB Output is correct
18 Correct 3 ms 1916 KB Output is correct
19 Correct 2 ms 1916 KB Output is correct
20 Correct 2 ms 1916 KB Output is correct
21 Correct 8 ms 6524 KB Output is correct
22 Correct 8 ms 6524 KB Output is correct
23 Correct 8 ms 6524 KB Output is correct
24 Correct 8 ms 6580 KB Output is correct
25 Correct 8 ms 6580 KB Output is correct
26 Correct 8 ms 6580 KB Output is correct
27 Correct 8 ms 6580 KB Output is correct
28 Correct 6 ms 6580 KB Output is correct
29 Correct 3 ms 6580 KB Output is correct
30 Correct 9 ms 6580 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 428 KB Output is correct
4 Correct 2 ms 428 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 2 ms 520 KB Output is correct
8 Correct 2 ms 592 KB Output is correct
9 Correct 2 ms 592 KB Output is correct
10 Correct 2 ms 720 KB Output is correct
11 Correct 2 ms 996 KB Output is correct
12 Correct 3 ms 1892 KB Output is correct
13 Correct 3 ms 1892 KB Output is correct
14 Correct 3 ms 1900 KB Output is correct
15 Correct 3 ms 1900 KB Output is correct
16 Correct 3 ms 1916 KB Output is correct
17 Correct 2 ms 1916 KB Output is correct
18 Correct 3 ms 1916 KB Output is correct
19 Correct 2 ms 1916 KB Output is correct
20 Correct 2 ms 1916 KB Output is correct
21 Correct 8 ms 6524 KB Output is correct
22 Correct 8 ms 6524 KB Output is correct
23 Correct 8 ms 6524 KB Output is correct
24 Correct 8 ms 6580 KB Output is correct
25 Correct 8 ms 6580 KB Output is correct
26 Correct 8 ms 6580 KB Output is correct
27 Correct 8 ms 6580 KB Output is correct
28 Correct 6 ms 6580 KB Output is correct
29 Correct 3 ms 6580 KB Output is correct
30 Correct 9 ms 6580 KB Output is correct
31 Runtime error 84 ms 56064 KB Execution killed with signal 11 (could be triggered by violating memory limits)
32 Halted 0 ms 0 KB -