oj.uz

답안 #814968

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
814968 2023-08-08T11:27:42 Z makanhulia Tents (JOI18_tents) C++17
48 / 100
 415 ms 502576 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

# 결과 실행 시간 메모리 Grader output
1 Correct 172 ms 502456 KB Output is correct
2 Correct 162 ms 502424 KB Output is correct
3 Correct 154 ms 502412 KB Output is correct
4 Correct 156 ms 502460 KB Output is correct
5 Correct 174 ms 502404 KB Output is correct
6 Correct 171 ms 502520 KB Output is correct
7 Correct 160 ms 502436 KB Output is correct
8 Correct 161 ms 502500 KB Output is correct
9 Correct 158 ms 502440 KB Output is correct
10 Correct 214 ms 502444 KB Output is correct
11 Correct 156 ms 502508 KB Output is correct
12 Correct 415 ms 502576 KB Output is correct

Subtask #2
0 / 52.0

# 결과 실행 시간 메모리 Grader output
1 Correct 172 ms 502456 KB Output is correct
2 Correct 162 ms 502424 KB Output is correct
3 Correct 154 ms 502412 KB Output is correct
4 Correct 156 ms 502460 KB Output is correct
5 Correct 174 ms 502404 KB Output is correct
6 Correct 171 ms 502520 KB Output is correct
7 Correct 160 ms 502436 KB Output is correct
8 Correct 161 ms 502500 KB Output is correct
9 Correct 158 ms 502440 KB Output is correct
10 Correct 214 ms 502444 KB Output is correct
11 Correct 156 ms 502508 KB Output is correct
12 Correct 415 ms 502576 KB Output is correct
13 Correct 153 ms 502500 KB Output is correct
14 Incorrect 163 ms 502564 KB Output isn't correct
15 Halted 0 ms 0 KB -