oj.uz

Submission #830784

# Submission time Handle Problem Language Result Execution time Memory
830784 2023-08-19T10:34:05 Z vjudge1 Tents (JOI18_tents) C++17
48 / 100
 2000 ms 126828 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][3001][3001];
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 23 ms 46676 KB Output is correct
2 Correct 25 ms 48596 KB Output is correct
3 Correct 29 ms 46592 KB Output is correct
4 Correct 24 ms 46588 KB Output is correct
5 Correct 39 ms 49628 KB Output is correct
6 Correct 40 ms 47632 KB Output is correct
7 Correct 35 ms 49072 KB Output is correct
8 Correct 28 ms 47028 KB Output is correct
9 Correct 24 ms 46624 KB Output is correct
10 Correct 55 ms 48004 KB Output is correct
11 Correct 26 ms 50384 KB Output is correct
12 Correct 137 ms 50428 KB Output is correct

Subtask #2
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 46676 KB Output is correct
2 Correct 25 ms 48596 KB Output is correct
3 Correct 29 ms 46592 KB Output is correct
4 Correct 24 ms 46588 KB Output is correct
5 Correct 39 ms 49628 KB Output is correct
6 Correct 40 ms 47632 KB Output is correct
7 Correct 35 ms 49072 KB Output is correct
8 Correct 28 ms 47028 KB Output is correct
9 Correct 24 ms 46624 KB Output is correct
10 Correct 55 ms 48004 KB Output is correct
11 Correct 26 ms 50384 KB Output is correct
12 Correct 137 ms 50428 KB Output is correct
13 Correct 71 ms 114248 KB Output is correct
14 Correct 25 ms 46600 KB Output is correct
15 Execution timed out 2101 ms 126828 KB Time limit exceeded
16 Halted 0 ms 0 KB -