oj.uz

Submission #931393

# Submission time Handle Problem Language Result Execution time Memory
931393 2024-02-21T17:38:50 Z alexander707070 Tents (JOI18_tents) C++14
48 / 100
 164 ms 245460 KB 
#include<bits/stdc++.h>
#define MAXN 307
using namespace std;

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

bool li[MAXN][MAXN][MAXN];
long long dp[MAXN][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>=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,long long e){
    if(n==0){
        return ff2(e,m);
    }

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

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

    dp[n][m][e]%=mod;

    return dp[n][m][e];    
}

int main(){

    cin>>n>>m;

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

    return 0;
}

Subtask #1
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 28 ms 35408 KB Output is correct
4 Correct 125 ms 157364 KB Output is correct
5 Correct 8 ms 51024 KB Output is correct
6 Correct 37 ms 176960 KB Output is correct
7 Correct 13 ms 70996 KB Output is correct
8 Correct 45 ms 194316 KB Output is correct
9 Correct 10 ms 93276 KB Output is correct
10 Correct 92 ms 227784 KB Output is correct
11 Correct 2 ms 8536 KB Output is correct
12 Correct 164 ms 245460 KB Output is correct

Subtask #2
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 28 ms 35408 KB Output is correct
4 Correct 125 ms 157364 KB Output is correct
5 Correct 8 ms 51024 KB Output is correct
6 Correct 37 ms 176960 KB Output is correct
7 Correct 13 ms 70996 KB Output is correct
8 Correct 45 ms 194316 KB Output is correct
9 Correct 10 ms 93276 KB Output is correct
10 Correct 92 ms 227784 KB Output is correct
11 Correct 2 ms 8536 KB Output is correct
12 Correct 164 ms 245460 KB Output is correct
13 Correct 1 ms 2392 KB Output is correct
14 Runtime error 5 ms 348 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -