oj.uz

Submission #814919

# Submission time Handle Problem Language Result Execution time Memory
814919 2023-08-08T11:08:56 Z andecaandeci Tents (JOI18_tents) C++17
48 / 100
 616 ms 524288 KB 
#include <bits/stdc++.h>
#define int long long
#define REP(i,o,n) for(int i=o;i<n;i++)
#define pb push_back
#define fi first
#define se second
#define FORI(v) for(auto i:v)
#define FORJ(v) for(auto j:v)
#define SETIO cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false);
using namespace std;
using pii = pair<int, int>;

const int mod = 1e9+7;
const int mi2 = (mod+1)/2;
int memo[400][400][400];
// int memo2[4000][4000];

// R-e-m---i-s---d-e-p-e-n-d-e-n-t---o-n---z-e-r-o---a-n-d---o-n-e-?-?-?-?-?-
int dp(int zero, int one, int rem) {
    if(zero<0)return 0;
    if(one<0)return 0;
    if(rem<0)return 0;
    if(rem==0){
        int a = 1;
        REP(i,0,one)a*=4,a%=mod;
        return a;
    }
    
    int &ans=memo[zero][one][rem];
    if(ans!=-1)return ans;
    ans=0;
    ans=dp(zero-2,one,rem-1)*(((zero*(zero-1)))%mod); // Ambil 2
    ans%=mod;
    ans*=mi2;
    ans%=mod;
    ans+=dp(zero-1,one+1,rem-1)*((zero)%mod); // Ambil satu baru
    ans%=mod;
    ans+=dp(zero,one-1,rem-1)*((one)%mod); // Sambung yang lama
    ans%=mod;
    ans+=dp(zero,one,rem-1); // _Nothing_
    ans%=mod;   
    return ans;
}

// int ncr(int n, int r){
//     if(n<r)return 0;
//     if(n<0)return 0;
//     if(r<0)return 0;

//     if(n==r)return 1;
//     if(n==0)return 1;
//     if(r==0)return 1;
//     if(r==1)return n;
//     if(n==1)return 1;

//     auto&ans=memo2[n][r];
//     if(ans!=-1)return ans;
//     return ans=((ncr(n-1,r)+ncr(n-1,r-1))%mod);
// }

#undef int
int main() 
#define int long long
{
    int h, w;cin>>h>>w;
    memset(memo,-1,sizeof memo);
    // memset(memo2,-1,sizeof memo2);
    // int ans=0;
    // REP(i,0,h+1){
    //     int res=ncr(h,i);
    //     res*=dp(w,0,h-i);
    //     res%=mod;
    //     ans+=res;
    //     ans%=mod;
    // }
    // ans--;
    // if(ans==-1)ans=(mod-1);
    int ans=dp(w,0,h);
    if(ans==0)ans=mod-1;
    else ans--;
    cout<<ans<<endl;
}

Subtask #1
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 501228 KB Output is correct
2 Correct 148 ms 501196 KB Output is correct
3 Correct 165 ms 501188 KB Output is correct
4 Correct 157 ms 501256 KB Output is correct
5 Correct 149 ms 501176 KB Output is correct
6 Correct 171 ms 501224 KB Output is correct
7 Correct 161 ms 501200 KB Output is correct
8 Correct 158 ms 501192 KB Output is correct
9 Correct 149 ms 501164 KB Output is correct
10 Correct 209 ms 501268 KB Output is correct
11 Correct 149 ms 501196 KB Output is correct
12 Correct 402 ms 501268 KB Output is correct

Subtask #2
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 501228 KB Output is correct
2 Correct 148 ms 501196 KB Output is correct
3 Correct 165 ms 501188 KB Output is correct
4 Correct 157 ms 501256 KB Output is correct
5 Correct 149 ms 501176 KB Output is correct
6 Correct 171 ms 501224 KB Output is correct
7 Correct 161 ms 501200 KB Output is correct
8 Correct 158 ms 501192 KB Output is correct
9 Correct 149 ms 501164 KB Output is correct
10 Correct 209 ms 501268 KB Output is correct
11 Correct 149 ms 501196 KB Output is correct
12 Correct 402 ms 501268 KB Output is correct
13 Runtime error 616 ms 524288 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -