oj.uz

Submission #246637

# Submission time Handle Problem Language Result Execution time Memory
246637 2020-07-09T20:02:27 Z fivefourthreeone Tents (JOI18_tents) C++17
100 / 100
 109 ms 70776 KB 
#include <bits/stdc++.h>
#define owo(i,a, b) for(int i=(a); i<(b); ++i)
#define uwu(i,a, b) for(int i=(a)-1; i>=(b); --i)
#define senpai push_back
#define ttgl pair<int, int>
#define ayaya cout<<"debug"<<endl
 
using namespace std;
using ll = long long;
using ld = long double;
const ll MOD = 1e9+7;
const double PI = acos(-1);
const int INF = 0x3f3f3f3f;
const int NINF = 0x3f3f3f40;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const ll NINFLL = 0x3f3f3f3f3f3f3f40;
const int mxN = 3001;
ll dp[mxN][mxN];
int n, m;
int main()
{
    //freopen("filename.in", "r", stdin);
    //freopen("filename.out", "w", stdout);
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>m;
    owo(i, 0, n+1) {
        owo(j, 0, m+1) {
            if(i==0||j==0) dp[i][j]=1;
            else {
                dp[i][j] = dp[i-1][j];
                dp[i][j] = (dp[i][j]+4LL*dp[i-1][j-1]*j)%MOD;
                if(j>1) {
                    dp[i][j] = (dp[i][j] + dp[i-1][j-2]*1LL*j*(j-1)/2)%MOD;
                }
                if(i>1) {
                    dp[i][j] = (dp[i][j] + dp[i-2][j-1]*1LL*j*(i-1))%MOD;
                }
            }
            //cout<<i<<" "<<j<<" "<<dp[i][j]<<"\n";
        }
    }
    cout<<(dp[n][m]-1)<<"\n";
    return 0;
}

Subtask #1
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 5 ms 1280 KB Output is correct
5 Correct 5 ms 768 KB Output is correct
6 Correct 5 ms 1408 KB Output is correct
7 Correct 5 ms 896 KB Output is correct
8 Correct 5 ms 1536 KB Output is correct
9 Correct 5 ms 896 KB Output is correct
10 Correct 6 ms 1792 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 7 ms 2304 KB Output is correct

Subtask #2
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 5 ms 1280 KB Output is correct
5 Correct 5 ms 768 KB Output is correct
6 Correct 5 ms 1408 KB Output is correct
7 Correct 5 ms 896 KB Output is correct
8 Correct 5 ms 1536 KB Output is correct
9 Correct 5 ms 896 KB Output is correct
10 Correct 6 ms 1792 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 7 ms 2304 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 9 ms 9728 KB Output is correct
15 Correct 89 ms 55288 KB Output is correct
16 Correct 9 ms 4096 KB Output is correct
17 Correct 21 ms 12928 KB Output is correct
18 Correct 24 ms 17152 KB Output is correct
19 Correct 86 ms 63096 KB Output is correct
20 Correct 70 ms 51064 KB Output is correct
21 Correct 48 ms 33784 KB Output is correct
22 Correct 49 ms 35448 KB Output is correct
23 Correct 32 ms 27136 KB Output is correct
24 Correct 109 ms 70776 KB Output is correct
25 Correct 88 ms 61176 KB Output is correct
26 Correct 96 ms 66552 KB Output is correct
27 Correct 107 ms 68948 KB Output is correct