oj.uz

Submission #59562

# Submission time Handle Problem Language Result Execution time Memory
59562 2018-07-22T11:08:51 Z theknife2001 Tents (JOI18_tents) C++17
48 / 100
 1511 ms 222764 KB 
#include <bits/stdc++.h>

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

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

    dp[i][j0][j1]=x;
    return x;
}


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

Subtask #1
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 222328 KB Output is correct
2 Correct 191 ms 222440 KB Output is correct
3 Correct 176 ms 222528 KB Output is correct
4 Correct 201 ms 222744 KB Output is correct
5 Correct 205 ms 222744 KB Output is correct
6 Correct 260 ms 222744 KB Output is correct
7 Correct 196 ms 222744 KB Output is correct
8 Correct 236 ms 222748 KB Output is correct
9 Correct 178 ms 222748 KB Output is correct
10 Correct 480 ms 222764 KB Output is correct
11 Correct 178 ms 222764 KB Output is correct
12 Correct 1511 ms 222764 KB Output is correct

Subtask #2
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 222328 KB Output is correct
2 Correct 191 ms 222440 KB Output is correct
3 Correct 176 ms 222528 KB Output is correct
4 Correct 201 ms 222744 KB Output is correct
5 Correct 205 ms 222744 KB Output is correct
6 Correct 260 ms 222744 KB Output is correct
7 Correct 196 ms 222744 KB Output is correct
8 Correct 236 ms 222748 KB Output is correct
9 Correct 178 ms 222748 KB Output is correct
10 Correct 480 ms 222764 KB Output is correct
11 Correct 178 ms 222764 KB Output is correct
12 Correct 1511 ms 222764 KB Output is correct
13 Correct 199 ms 222764 KB Output is correct
14 Incorrect 189 ms 222764 KB Output isn't correct
15 Halted 0 ms 0 KB -