답안 #59590

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
59590	2018-07-22T14:33:11 Z	theknife2001	Tents (JOI18_tents)	C++17	100 / 100	1047 ms	71688 KB

tents

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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