oj.uz

Submission #229683

# Submission time Handle Problem Language Result Execution time Memory
229683 2020-05-05T21:52:26 Z DS007 Tents (JOI18_tents) C++14
0 / 100
 6 ms 1024 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] += (i - 1) * (i - 2) / 2 * (j - 1) * (j - 2) / 2 * ((i >= 3) * (j >= 3) * (dp[i - 3][j - 3] + 1));
            dp[i][j] += (i - 1) * (dp[i - 2][j - 1] + 1);
            dp[i][j] += (j - 1) * (dp[i - 1][j - 2] + 1);
            dp[i][j] += dp[i - 1][j - 1];
            dp[i][j] += (i - 1) * (j - 1) * 2 * (dp[i - 2][j - 2] + 1);
            dp[i][j] += (i - 1) * (j - 1) * (j - 2) * (i - 2) * ((i >= 3) * (j >= 3) * (dp[i - 3][j - 3] + 1));
            dp[i][j] += (i - 1) * (i - 2) / 2 * (dp[i - 3][j - 1] + 1);
            dp[i][j] += (j - 1) * (j - 2) / 2 * (dp[i - 1][j - 3] + 1);
            dp[i][j] += (i - 1) * (i - 2) / 2 * (j - 1) * (i - 3) * (dp[i - 4][j - 2] + 1);
            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:42:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

Subtask #1
0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 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 5 ms 512 KB Output is correct
8 Correct 5 ms 512 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 640 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Incorrect 6 ms 1024 KB Output isn't correct

Subtask #2
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 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 5 ms 512 KB Output is correct
8 Correct 5 ms 512 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 640 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Incorrect 6 ms 1024 KB Output isn't correct