oj.uz

Submission #830760

# Submission time Handle Problem Language Result Execution time Memory
830760 2023-08-19T10:10:07 Z vjudge1 Tents (JOI18_tents) C++17
0 / 100
 1 ms 1848 KB 
#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;
const int mod = 1e9+7;
ll dp[2][301][301];
ll hiy[301][301];
int main() {
    int H,W;
    cin >> H >> W;
    dp[0][0][0] = 1;
    for(int i=0; i<=300; i++) {
        hiy[i][0] = 1;
        for(int j=1; j<=i; j++) {
            hiy[i][j] = hiy[i-1][j-1] + hiy[i-1][j];
            hiy[i][j]%=mod;
        }
    }
    for(int i=0; i<H; i++) {
        for(int j=0; j<W; j++) {
            for(int k=0; k<=W; k++) {
                if(dp[0][j][k]==0) continue;
                int xp = W-k-j;
                if(k!=0) {
                    dp[1][j+1][k-1]+=dp[0][j][k] * k%mod;
                    dp[1][j+1][k-1]%=mod;
                }
                if(xp!=0) {
                    dp[1][j+1][k]+=dp[0][j][k] * 3 * xp%mod;
                    dp[1][j+1][k]%=mod;
                    dp[1][j][k+1]+=dp[0][j][k] * xp%mod;
                    dp[1][j][k+1]%=mod;
                }
                if(xp>=2) {
                    dp[1][j+2][k]+=dp[0][j][k] * 1LL * hiy[xp][2]%mod;
                    dp[1][j+2][k]%=mod;
                }
                dp[1][j][k]+=dp[0][j][k];
                dp[1][j][k]%=mod;
            }
        }
        for(int j=0; j<=W; j++) {
            for(int k=0; k<=W; k++) {
                dp[0][j][k] = dp[1][j][k];
                dp[1][j][k] = 0;
            }
        }
    }
    ll jwb = 0;
    for(int i=0; i<=W; i++) {
        for(int j=0; j<=W; j++) {
            jwb+=dp[0][i][j];
            jwb%=mod;
        }
    }
    jwb+=(mod-1);
    jwb%=mod;
    cout << jwb << endl;
    return 0;
}

Subtask #1
0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1076 KB Output is correct
2 Correct 1 ms 1848 KB Output is correct
3 Incorrect 1 ms 980 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1076 KB Output is correct
2 Correct 1 ms 1848 KB Output is correct
3 Incorrect 1 ms 980 KB Output isn't correct
4 Halted 0 ms 0 KB -