oj.uz

Submission #814972

# Submission time Handle Problem Language Result Execution time Memory
814972 2023-08-08T11:29:19 Z christinelynn Tents (JOI18_tents) C++17
48 / 100
 606 ms 502652 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[400][400];

// 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[one][zero][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){
        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 183 ms 502424 KB Output is correct
2 Correct 151 ms 502508 KB Output is correct
3 Correct 150 ms 502500 KB Output is correct
4 Correct 148 ms 502460 KB Output is correct
5 Correct 153 ms 502492 KB Output is correct
6 Correct 177 ms 502424 KB Output is correct
7 Correct 163 ms 502424 KB Output is correct
8 Correct 171 ms 502412 KB Output is correct
9 Correct 149 ms 502432 KB Output is correct
10 Correct 258 ms 502520 KB Output is correct
11 Correct 149 ms 502428 KB Output is correct
12 Correct 606 ms 502488 KB Output is correct

Subtask #2
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 502424 KB Output is correct
2 Correct 151 ms 502508 KB Output is correct
3 Correct 150 ms 502500 KB Output is correct
4 Correct 148 ms 502460 KB Output is correct
5 Correct 153 ms 502492 KB Output is correct
6 Correct 177 ms 502424 KB Output is correct
7 Correct 163 ms 502424 KB Output is correct
8 Correct 171 ms 502412 KB Output is correct
9 Correct 149 ms 502432 KB Output is correct
10 Correct 258 ms 502520 KB Output is correct
11 Correct 149 ms 502428 KB Output is correct
12 Correct 606 ms 502488 KB Output is correct
13 Correct 150 ms 502416 KB Output is correct
14 Incorrect 159 ms 502652 KB Output isn't correct
15 Halted 0 ms 0 KB -