oj.uz

Submission #830781

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

Subtask #1
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 46676 KB Output is correct
2 Correct 25 ms 47444 KB Output is correct
3 Correct 24 ms 46532 KB Output is correct
4 Correct 23 ms 46600 KB Output is correct
5 Correct 30 ms 47764 KB Output is correct
6 Correct 35 ms 46988 KB Output is correct
7 Correct 32 ms 47560 KB Output is correct
8 Correct 29 ms 46856 KB Output is correct
9 Correct 23 ms 46572 KB Output is correct
10 Correct 55 ms 47240 KB Output is correct
11 Correct 25 ms 47948 KB Output is correct
12 Correct 130 ms 47992 KB Output is correct

Subtask #2
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 46676 KB Output is correct
2 Correct 25 ms 47444 KB Output is correct
3 Correct 24 ms 46532 KB Output is correct
4 Correct 23 ms 46600 KB Output is correct
5 Correct 30 ms 47764 KB Output is correct
6 Correct 35 ms 46988 KB Output is correct
7 Correct 32 ms 47560 KB Output is correct
8 Correct 29 ms 46856 KB Output is correct
9 Correct 23 ms 46572 KB Output is correct
10 Correct 55 ms 47240 KB Output is correct
11 Correct 25 ms 47948 KB Output is correct
12 Correct 130 ms 47992 KB Output is correct
13 Runtime error 78 ms 94188 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -