Submission #1082752

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082752		toast12	Tents (JOI18_tents)	C++14	100 / 100	211 ms	72596 KiB

tents

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int MOD = 1e9+7;

vector<vector<bool>> ready;
vector<vector<ll>> dp;

// there are h rows and w columns left
ll solve(int h, int w) {
    if (h < 0 || w < 0)
        return 0;
    if (h == 0 || w == 0)
        return 1;
    if (ready[h][w])
        return dp[h][w];
    ll ans = 0;
    // place nothing
    ans += solve(h-1, w);
    ans %= MOD;
    // place one tent in this row
    // this eliminates one row, one column, and there are 4 different directions the opening can be
    ans += 4*solve(h-1, w-1)*w;
    ans %= MOD;
    // place two tents in this row
    // this eliminates one row, two columns and you can place the two tents in w choose 2 different ways
    ans += solve(h-1, w-2)*(w*(w-1)/2);
    ans %= MOD;
    // place two tents in one column, but one of them is in this row
    // this eliminates two rows, one column and you can choose the column w ways and choose the other row (h-1) ways
    ans += solve(h-2, w-1)*w*(h-1);
    ans %= MOD;
    ready[h][w] = true;
    return dp[h][w] = ans;
}

int main() {
    int h, w;
    cin >> h >> w;
    ready.resize(h+1, vector<bool>(w+1));
    dp.resize(h+1, vector<ll>(w+1));
    cout << (solve(h, w)+MOD-1) % MOD << '\n';
    return 0;   
}

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