제출 #1324273

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1324273		sh_qaxxorov_571	Tents (JOI18_tents)	C++20	100 / 100	82 ms	70864 KiB

tents

#include <iostream>
#include <vector>

using namespace std;

/**
 * JOI 2017/2018 Spring Training Camp - Tents
 * Dinamik dasturlash O(H*W)
 */

long long dp[3005][3005];
const int MOD = 1000000007;

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

    // Baza holati: 0 ta qator yoki 0 ta ustun bo'lsa, 1 ta usul (bo'sh holat)
    for (int j = 0; j <= W; j++) dp[0][j] = 1;
    for (int i = 0; i <= H; i++) dp[i][0] = 1;

    for (int i = 1; i <= H; i++) {
        for (int j = 1; j <= W; j++) {
            // 1. Birinchi qator bo'sh
            dp[i][j] = dp[i-1][j];

            // 2. Birinchi qatorda 1 ta chodir (4 yo'nalishdan biri)
            dp[i][j] = (dp[i][j] + 4LL * j * dp[i-1][j-1]) % MOD;

            // 3. Birinchi qatorda 2 ta chodir (Sharq-G'arb juftligi)
            if (j >= 2) {
                long long combinations = (1LL * j * (j - 1) / 2) % MOD;
                dp[i][j] = (dp[i][j] + combinations * dp[i-1][j-2]) % MOD;
            }

            // 4. Birinchi qatordagi chodir boshqa bir qatordagi bilan juftlashgan (Shimol-Janub)
            if (i >= 2) {
                long long row_col_choices = (1LL * j * (i - 1)) % MOD;
                dp[i][j] = (dp[i][j] + row_col_choices * dp[i-2][j-1]) % MOD;
            }
        }
    }

    // Natija: kamida bitta chodir bo'lishi kerak, shuning uchun bo'sh holatni (1) ayiramiz
    long long result = (dp[H][W] - 1 + MOD) % MOD;
    cout << result << endl;

    return 0;
}

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