oj.uz

Submission #229684

# Submission time Handle Problem Language Result Execution time Memory
229684 2020-05-05T21:54:58 Z DS007 Tents (JOI18_tents) C++14
48 / 100
 246 ms 44260 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long

const int mod = 1e9 + 7;

int solveTestCase(int test) {
    int h, w;
    cin >> h >> w;

    int dp[h + 1][w + 1] = {};
    dp[1][1] = 4;

    for (int i = 2; i <= h; i++) {
        dp[i][1] = i * 4 + i * (i - 1) / 2;
        dp[i][1] %= mod;
    }

    for (int i = 2; i <= w; i++) {
        dp[1][i] = i * 4 + i * (i - 1) / 2;
        dp[1][i] %= mod;
    }

    for (int i = 2; i <= h; i++) {
        for (int j = 2; j <= w; j++) {
            dp[i][j] += (i + j - 1) * 4 * (dp[i - 1][j - 1] + 1) - (i - 1) * (j - 1) * 16 * (dp[i - 2][j - 2] + 1);
            dp[i][j] %= mod;
            dp[i][j] += (i - 1) * (i - 2) / 2 * (j - 1) * (j - 2) / 2 * ((i >= 3) * (j >= 3) * dp[i - 3][j - 3] + 1);
            dp[i][j] %= mod;
            dp[i][j] += (i - 1) * (dp[i - 2][j - 1] + 1);
            dp[i][j] %= mod;
            dp[i][j] += (j - 1) * (dp[i - 1][j - 2] + 1);
            dp[i][j] %= mod;
            dp[i][j] += dp[i - 1][j - 1];
            dp[i][j] %= mod;
            dp[i][j] += (i - 1) * (j - 1) * 2 * (dp[i - 2][j - 2] + 1);
            dp[i][j] %= mod;
            dp[i][j] += (i - 1) * (j - 1) * (j - 2) * (i - 2) * ((i >= 3) * (j >= 3) * dp[i - 3][j - 3] + 1);
            dp[i][j] %= mod;
            dp[i][j] += (i - 1) * (i - 2) / 2 * (dp[i - 3][j - 1] + 1);
            dp[i][j] %= mod;
            dp[i][j] += (j - 1) * (j - 2) / 2 * (dp[i - 1][j - 3] + 1);
            dp[i][j] %= mod;
            dp[i][j] += (i - 1) * (i - 2) / 2 * (j - 1) * (i - 3) * (dp[i - 4][j - 2] + 1);
            dp[i][j] %= mod;
            dp[i][j] += (j - 1) * (j - 2) / 2 * (i - 1) * (j - 3) * (dp[i - 2][j - 4] + 1);
            dp[i][j] %= mod;
        }
    }

    cout << dp[h][w];
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int test = 1;
    // cin >> test;
    for (int i = 1; i <= test; i++)
        solveTestCase(i);
}

Compilation message

tents.cpp: In function 'long long int solveTestCase(long long int)':
tents.cpp:52:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

Subtask #1
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 5 ms 512 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 6 ms 512 KB Output is correct
8 Correct 6 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 7 ms 640 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 8 ms 1024 KB Output is correct

Subtask #2
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 5 ms 512 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 6 ms 512 KB Output is correct
8 Correct 6 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 7 ms 640 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 8 ms 1024 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Incorrect 246 ms 44260 KB Output isn't correct
16 Halted 0 ms 0 KB -