Submission #1163788

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163788		KK_1729	Tents (JOI18_tents)	C++17	100 / 100	106 ms	71112 KiB

tents

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

#define int long long
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define pb push_back
#define all(a) a.begin(), a.end()
#define endl "\n"

void printVector(vector<int> a){
    for (auto x: a) cout << x << " ";
    cout << endl;
}
int min(int x, int y){
    if (x < y) return x;
    return y;
}
vector<vector<int>> dp(3002, vector<int>(3002));

int val(int i, int j){
    // if (i <= 0 || j <= 0) return 0;
    return dp[i][j];
}
void solve(){
    
    int h, w; cin >> h >> w;
    

    int mod = 1000000007;
    FOR(j,0,w+1){
        dp[0][j] = 1;
        dp[1][j] = 1+4*j+ (j*(j-1))/2;
    }
    for (int i = 2; i <= h; i++){
        dp[i][0] = 1ll;
        dp[i][1] = 1ll + 4ll*i + (i*(i-1))/2ll;
        for (int j = 2; j <= w; ++j){

            
            dp[i][j] = ((dp[i][j-1] + 4*i * dp[i-1][j-1])%mod + (i*(i-1)/2 * dp[i-2][j-1] + i*(j-1) * dp[i-1][j-2])%mod)%mod;
            dp[i][j] %= mod;
        }
    }
    cout << dp[h][w]-1ll << endl;
}


int32_t main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int t = 1; // cin >> t;
    while (t--) solve();
}
// #include <iostream>
// using namespace std;

// int main()
// {
//     long long H, W;
//     cin >> H >> W;

//     long long m = 1000000007;

//     long long dp[H+1][W+1];

//         for(long long j = 0; j <= W; j++)
//         {
//             dp[0][j] = 1;
//             dp[1][j] = 1 + 4*j + j*(j-1)/2;
//         }
//     for(long long i = 2; i <= H; i++)
//     {
//         dp[i][0] = 1;
//         dp[i][1] = 1 + 4*i + i*(i-1)/2;
//         for(long long j = 2; j <= W; j++)
//         {
//             dp[i][j] = ((dp[i][j-1] + 4*i * dp[i-1][j-1])%m + (i*(i-1)/2 * dp[i-2][j-1] + i*(j-1) * dp[i-1][j-2])%m)%m;
//         }
//     }

//     cout << dp[H][W] - 1 << '\n';
// }

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