oj.uz

Submission #638398

# Submission time Handle Problem Language Result Execution time Memory
638398 2022-09-05T19:18:02 Z urosk Tents (JOI18_tents) C++14
100 / 100
 299 ms 70864 KB 
#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define ld double
#define ll long long
#define llinf 100000000000000000LL // 10^17
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) (ll)(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define daj_mi_malo_vremena ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);

using namespace std;
using namespace __gnu_pbds;
#define mod 1000000007

ll add(ll x,ll y){
    x+=y;
    if(x<0){
        x%=mod;
        x+=mod;
    }else{
        if(x>=mod) x%=mod;
    }
    return x;
}
ll mul(ll a,ll b){
	ll ans = (a*b)%mod;
	if(ans<0) ans+=mod;
	return ans;
}
ll po(ll x,ll y){
    if(y==0) return 1LL;
    ll ans = po(x,y/2);
    ans = mul(ans,ans);
    if(y&1) ans = mul(ans,x);
    return ans;
}
ll inv(ll x){return po(x,mod-2);}
ll ch(ll x){
    return mul(mul(x,x-1),inv(2));
}
#define maxn 3005
ll n,m;
ll dp[maxn][maxn];
void tc(){
    cin >> n >> m;
    for(ll i = 0;i<maxn;i++) dp[i][0] = dp[0][i] = 1;
    for(ll i = 1;i<=n;i++){
        for(ll j = 1;j<=m;j++){
            dp[i][j] = add(dp[i][j],dp[i-1][j]);
            dp[i][j] = add(dp[i][j],mul(dp[i-1][j-1],4*j));
            if(i>=2) dp[i][j] = add(dp[i][j],mul(dp[i-2][j-1],mul(j,i-1)));
            if(j>=2) dp[i][j] = add(dp[i][j],mul(dp[i-1][j-2],j*(j-1)/2));
        }
    }
    dp[n][m] = add(dp[n][m],-1);
    cout<<dp[n][m]<<endl;
}
int main(){
	daj_mi_malo_vremena
    int t; t = 1;
    while(t--){
        tc();
    }
	return 0;
}

Subtask #1
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12500 KB Output is correct
2 Correct 5 ms 12372 KB Output is correct
3 Correct 5 ms 12500 KB Output is correct
4 Correct 5 ms 12500 KB Output is correct
5 Correct 5 ms 12616 KB Output is correct
6 Correct 5 ms 12628 KB Output is correct
7 Correct 5 ms 12612 KB Output is correct
8 Correct 5 ms 12500 KB Output is correct
9 Correct 5 ms 12500 KB Output is correct
10 Correct 6 ms 12756 KB Output is correct
11 Correct 5 ms 12488 KB Output is correct
12 Correct 8 ms 13152 KB Output is correct

Subtask #2
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12500 KB Output is correct
2 Correct 5 ms 12372 KB Output is correct
3 Correct 5 ms 12500 KB Output is correct
4 Correct 5 ms 12500 KB Output is correct
5 Correct 5 ms 12616 KB Output is correct
6 Correct 5 ms 12628 KB Output is correct
7 Correct 5 ms 12612 KB Output is correct
8 Correct 5 ms 12500 KB Output is correct
9 Correct 5 ms 12500 KB Output is correct
10 Correct 6 ms 12756 KB Output is correct
11 Correct 5 ms 12488 KB Output is correct
12 Correct 8 ms 13152 KB Output is correct
13 Correct 4 ms 12500 KB Output is correct
14 Correct 5 ms 12500 KB Output is correct
15 Correct 168 ms 56048 KB Output is correct
16 Correct 15 ms 15212 KB Output is correct
17 Correct 44 ms 22184 KB Output is correct
18 Correct 52 ms 24524 KB Output is correct
19 Correct 200 ms 63308 KB Output is correct
20 Correct 159 ms 53124 KB Output is correct
21 Correct 106 ms 39156 KB Output is correct
22 Correct 106 ms 38776 KB Output is correct
23 Correct 63 ms 27112 KB Output is correct
24 Correct 264 ms 70864 KB Output is correct
25 Correct 219 ms 62804 KB Output is correct
26 Correct 265 ms 67276 KB Output is correct
27 Correct 299 ms 69332 KB Output is correct