oj.uz

Submission #810191

# Submission time Handle Problem Language Result Execution time Memory
810191 2023-08-06T06:17:30 Z winter0101 Tents (JOI18_tents) C++14
48 / 100
 2000 ms 81924 KB 
#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define pil pair<int,long long>
#define pll pair<long long,long long>
#define eb emplace_back
const long long du=1e9+7;
long long f[3001][3001];
long long combi[3001][3001];
long long pw[3001];
long long fact[6001];
long long inv[6001];
long long pow(long long a, long long b, long long m) {
    a %= m;
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("temp.INP","r",stdin);
    //freopen("temp.OUT","w",stdout);
    int m,n;
    cin>>m>>n;
    pw[0]=1;
    for1(i,1,3000)pw[i]=(pw[i-1]*4)%du;
    fact[0]=1;
    for1(i,1,6000)fact[i]=(fact[i-1]*i)%du;
    for1(i,0,6000){
    inv[i]=pow(fact[i],du-2,du);
    }
    combi[0][0]=1;
    for1(i,1,3000){
    combi[i][0]=1;
    for1(j,1,3000){
    combi[i][j]=(combi[i-1][j-1]+combi[i-1][j])%du;
    }
    }
    f[0][0]=1;
    for1(i,0,m){
    for1(j,0,n){
    if (!f[i][j])continue;
    int t1=j*2+i,t2=i*2+j;
    if (t1>m||t2>n){
        f[i][j]=0;
        continue;
    }
    if (t1+1<=m&&t2+2<=n){
        long long dd=(combi[m-t1][1]*combi[n-t2][2])%du;
        f[i+1][j]=(f[i+1][j]+f[i][j]*dd)%du;
    }
    if (t1+2<=m&&t2+1<=n){
        long long dd=(combi[m-t1][2]*combi[n-t2][1])%du;
        f[i][j+1]=(f[i][j+1]+f[i][j]*dd)%du;
    }
    }
    }
    for1(i,0,m){
    for1(j,0,n){
    if (!f[i][j])continue;
    f[i][j]=(f[i][j]*inv[i+j])%du;
    }
    }
    long long ans=0;
    for1(i,0,m){
    for1(j,0,n){
    if (!f[i][j])continue;
    int t1=j*2+i,t2=i*2+j;
    int l1=m-t1,l2=n-t2;
    for1(k,0,min(l1,l2)){
        long long dd=(pw[k]*combi[l1][k])%du;
        dd=(dd*combi[l2][k])%du;
        dd=(dd*fact[k])%du;
        ans=(ans+f[i][j]*dd)%du;
    }
    }
    }
    cout<<(ans-1+du)%du;

}

Subtask #1
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 70844 KB Output is correct
2 Correct 41 ms 70912 KB Output is correct
3 Correct 37 ms 70860 KB Output is correct
4 Correct 35 ms 70920 KB Output is correct
5 Correct 36 ms 71160 KB Output is correct
6 Correct 39 ms 71064 KB Output is correct
7 Correct 35 ms 71276 KB Output is correct
8 Correct 35 ms 71028 KB Output is correct
9 Correct 36 ms 70912 KB Output is correct
10 Correct 39 ms 71108 KB Output is correct
11 Correct 36 ms 70840 KB Output is correct
12 Correct 47 ms 71628 KB Output is correct

Subtask #2
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 70844 KB Output is correct
2 Correct 41 ms 70912 KB Output is correct
3 Correct 37 ms 70860 KB Output is correct
4 Correct 35 ms 70920 KB Output is correct
5 Correct 36 ms 71160 KB Output is correct
6 Correct 39 ms 71064 KB Output is correct
7 Correct 35 ms 71276 KB Output is correct
8 Correct 35 ms 71028 KB Output is correct
9 Correct 36 ms 70912 KB Output is correct
10 Correct 39 ms 71108 KB Output is correct
11 Correct 36 ms 70840 KB Output is correct
12 Correct 47 ms 71628 KB Output is correct
13 Correct 35 ms 70828 KB Output is correct
14 Correct 40 ms 71004 KB Output is correct
15 Execution timed out 2056 ms 81924 KB Time limit exceeded
16 Halted 0 ms 0 KB -