oj.uz

Submission #931395

# Submission time Handle Problem Language Result Execution time Memory
931395 2024-02-21T17:48:51 Z alexander707070 Tents (JOI18_tents) C++14
100 / 100
 286 ms 159056 KB 
#include<bits/stdc++.h>
#define MAXN 3007
using namespace std;

long long n,m,nn,mm;
const long long mod=1e9+7;

bool li[MAXN][MAXN];
long long dp[MAXN][MAXN];

long long dp2[MAXN][MAXN];
bool li2[MAXN][MAXN];

long long ff2(long long n,long long m){
    if(m==0)return 1;

    if(li2[n][m])return dp2[n][m];
    li2[n][m]=true;

    dp2[n][m]=ff2(n,m-1);
    if(n>=1)dp2[n][m]+=ff2(n-1,m-1)*n*4;
    if(n>=2)dp2[n][m]+=ff2(n-2,m-1)*n*(n-1)/2;

    dp2[n][m]%=mod;

    return dp2[n][m];
}

long long ff(long long n,long long m){
    if(n==0){
        return ff2(nn-(mm-m)/2,m);
    }

    if(li[n][m])return dp[n][m];
    li[n][m]=true;

    dp[n][m]=ff(n-1,m);
    if(m>=2)dp[n][m]+=ff(n-1,m-2)*m*(m-1)/2;

    dp[n][m]%=mod;

    return dp[n][m];    
}

int main(){

    cin>>n>>m;
    nn=n; mm=m;

    cout<<ff(n,m)-1<<"\n";

    return 0;
}

Subtask #1
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 2 ms 11100 KB Output is correct
5 Correct 1 ms 6748 KB Output is correct
6 Correct 3 ms 15960 KB Output is correct
7 Correct 2 ms 9048 KB Output is correct
8 Correct 3 ms 15708 KB Output is correct
9 Correct 2 ms 8796 KB Output is correct
10 Correct 4 ms 20572 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 5 ms 20696 KB Output is correct

Subtask #2
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 2 ms 11100 KB Output is correct
5 Correct 1 ms 6748 KB Output is correct
6 Correct 3 ms 15960 KB Output is correct
7 Correct 2 ms 9048 KB Output is correct
8 Correct 3 ms 15708 KB Output is correct
9 Correct 2 ms 8796 KB Output is correct
10 Correct 4 ms 20572 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 5 ms 20696 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 20 ms 66840 KB Output is correct
15 Correct 176 ms 150244 KB Output is correct
16 Correct 9 ms 16256 KB Output is correct
17 Correct 30 ms 41368 KB Output is correct
18 Correct 43 ms 64584 KB Output is correct
19 Correct 199 ms 158036 KB Output is correct
20 Correct 154 ms 134092 KB Output is correct
21 Correct 92 ms 92396 KB Output is correct
22 Correct 104 ms 120228 KB Output is correct
23 Correct 37 ms 113492 KB Output is correct
24 Correct 286 ms 159056 KB Output is correct
25 Correct 202 ms 140996 KB Output is correct
26 Correct 244 ms 154656 KB Output is correct
27 Correct 281 ms 158336 KB Output is correct