Submission #708030

#	Time	Username	Problem	Language	Result	Execution time	Memory
708030		Spade1	Tents (JOI18_tents)	C++14	100 / 100	184 ms	70908 KiB

tents

#include<bits/stdc++.h>
//#include "grader.h"
#define pii pair<int, int>
#define pll pair<long long, long long>
#define ll long long
#define ld long double
#define st first
#define nd second
#define pb push_back
#define INF INT_MAX
using namespace std;

const int N = 3e3 + 10;
const int M = 1e9 + 7;
ll dp[N][N];

ll add(ll a, ll b) {return (((a+b)%M)+M)%M;}

void solve() {
    int h, w; cin >> h >> w;
    for (int i = 0; i <= h; ++i) dp[i][0] = 1;
    for (int j = 0; j <= w; ++j) dp[0][j] = 1;
    for (ll i = 1; i <= h; ++i) {
        for (ll j = 1; j <= w; ++j) {
            dp[i][j] = add(dp[i][j], dp[i-1][j]);
            dp[i][j] = add(dp[i][j], 4*j*dp[i-1][j-1]);
            if (i > 1) dp[i][j] = add(dp[i][j], (i-1)*j*dp[i-2][j-1]);
            if (j > 1) dp[i][j] = add(dp[i][j], j*(j-1)/2*dp[i-1][j-2]);
        }
    }
    cout << dp[h][w]-1 << '\n';
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(NULL);
    int t = 1;
//    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

• Subtask 1: 48 / 48
• Subtask 2: 52 / 52