oj.uz

Submission #59590

# Submission time Handle Problem Language Result Execution time Memory
59590 2018-07-22T14:33:11 Z theknife2001 Tents (JOI18_tents) C++17
100 / 100
 1047 ms 71688 KB 
#include <bits/stdc++.h>

using namespace std;
const int N=3005;
long long dp[N][N];
int n,m;
long long mod=1e9+7;

long long bt(int i, int j)
{
    if(i==n)
    {
        if(j==m)
            return 0;
        return 1;
    }
    if(dp[i][j]!=-1)
        return dp[i][j];
    long long x=bt(i+1,j);
    x%=mod;
    if(j)
        x+=bt(i+1,j-1)*4*j;
    x%=mod;
    if(j&&i+2<=n)
        x+=bt(i+2,j-1)*j*(n-i-1);
    x%=mod;
    if(j>1)
        x+=((bt(i+1,j-2)*j*(j-1))/2)%mod;
    x%=mod;

    dp[i][j]=x;
    return x;
}


int main()
{
    cin>>n>>m;
    memset(dp,-1,sizeof dp);
    cout<<bt(0,m)<<endl;
    return 0;
}

Subtask #1
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 71020 KB Output is correct
2 Correct 63 ms 71148 KB Output is correct
3 Correct 65 ms 71148 KB Output is correct
4 Correct 72 ms 71212 KB Output is correct
5 Correct 66 ms 71212 KB Output is correct
6 Correct 58 ms 71224 KB Output is correct
7 Correct 67 ms 71292 KB Output is correct
8 Correct 67 ms 71292 KB Output is correct
9 Correct 62 ms 71292 KB Output is correct
10 Correct 66 ms 71300 KB Output is correct
11 Correct 62 ms 71308 KB Output is correct
12 Correct 66 ms 71308 KB Output is correct

Subtask #2
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 71020 KB Output is correct
2 Correct 63 ms 71148 KB Output is correct
3 Correct 65 ms 71148 KB Output is correct
4 Correct 72 ms 71212 KB Output is correct
5 Correct 66 ms 71212 KB Output is correct
6 Correct 58 ms 71224 KB Output is correct
7 Correct 67 ms 71292 KB Output is correct
8 Correct 67 ms 71292 KB Output is correct
9 Correct 62 ms 71292 KB Output is correct
10 Correct 66 ms 71300 KB Output is correct
11 Correct 62 ms 71308 KB Output is correct
12 Correct 66 ms 71308 KB Output is correct
13 Correct 55 ms 71316 KB Output is correct
14 Correct 56 ms 71448 KB Output is correct
15 Correct 627 ms 71576 KB Output is correct
16 Correct 68 ms 71576 KB Output is correct
17 Correct 130 ms 71576 KB Output is correct
18 Correct 205 ms 71576 KB Output is correct
19 Correct 752 ms 71616 KB Output is correct
20 Correct 562 ms 71616 KB Output is correct
21 Correct 344 ms 71616 KB Output is correct
22 Correct 415 ms 71616 KB Output is correct
23 Correct 273 ms 71688 KB Output is correct
24 Correct 980 ms 71688 KB Output is correct
25 Correct 636 ms 71688 KB Output is correct
26 Correct 783 ms 71688 KB Output is correct
27 Correct 1047 ms 71688 KB Output is correct