oj.uz

Submission #1077668

# Submission time Handle Problem Language Result Execution time Memory
1077668 2024-08-27T08:32:38 Z nikolamanolov Tents (JOI18_tents) C++14
100 / 100
 212 ms 67664 KB 
#include<bits/stdc++.h>
using namespace std;
const long long MOD=1e9+7;
long long dp[3004][3004];
bool iz[3004][3004];
long long rec(long long i, long long j)
{
    if (i<0 || j<0) return 0;
    if (i==0 || j==0) return 1;

    if (iz[i][j]) return dp[i][j];

    long long ans=0;
    ans=(ans+rec(i-1, j))%MOD;
    ans=(ans+rec(i-1, j-1)*4*j)%MOD;
    ans=(ans+rec(i-1, j-2)*(j*(j-1)/2))%MOD;
    ans=(ans+rec(i-2, j-1)*j*(i-1))%MOD;
    iz[i][j]=true;
    return dp[i][j]=ans;
}

long long n, m;

int main ()
{
    cin>>n>>m;
    cout<<rec(n, m)-1<<endl;
}

Subtask #1
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 7004 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 7260 KB Output is correct
7 Correct 1 ms 4700 KB Output is correct
8 Correct 2 ms 9560 KB Output is correct
9 Correct 1 ms 4700 KB Output is correct
10 Correct 4 ms 9308 KB Output is correct
11 Correct 1 ms 2392 KB Output is correct
12 Correct 3 ms 4700 KB Output is correct

Subtask #2
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 7004 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 7260 KB Output is correct
7 Correct 1 ms 4700 KB Output is correct
8 Correct 2 ms 9560 KB Output is correct
9 Correct 1 ms 4700 KB Output is correct
10 Correct 4 ms 9308 KB Output is correct
11 Correct 1 ms 2392 KB Output is correct
12 Correct 3 ms 4700 KB Output is correct
13 Correct 1 ms 2392 KB Output is correct
14 Correct 10 ms 18264 KB Output is correct
15 Correct 142 ms 56544 KB Output is correct
16 Correct 4 ms 5464 KB Output is correct
17 Correct 14 ms 10072 KB Output is correct
18 Correct 42 ms 26196 KB Output is correct
19 Correct 184 ms 63820 KB Output is correct
20 Correct 130 ms 50268 KB Output is correct
21 Correct 74 ms 31316 KB Output is correct
22 Correct 84 ms 39480 KB Output is correct
23 Correct 77 ms 40528 KB Output is correct
24 Correct 204 ms 67664 KB Output is correct
25 Correct 152 ms 57428 KB Output is correct
26 Correct 180 ms 63312 KB Output is correct
27 Correct 212 ms 65628 KB Output is correct