oj.uz

Submission #44271

# Submission time Handle Problem Language Result Execution time Memory
44271 2018-03-31T06:03:09 Z RayaBurong25_1 Tents (JOI18_tents) C++17
48 / 100
 389 ms 216640 KB 
#include <stdio.h>
#define MOD 1000000007LL
long long DP[305][305][305];
long long E[305];
int min(int a, int b)
{
    return (a < b)?a:b;
}
int main()
{
    int H, W;
    scanf("%d %d", &H, &W);
    int i, j, k, l;
    DP[0][W][0] = 1;
    E[0] = 1;
    for (l = 1; l <= W; l++)
        E[l] = (E[l - 1]*4)%MOD;
    long long Ans = 0;
    for (i = 1; i <= H; i++)
    {
        for (j = 0; j <= W; j++)
        {
            for (k = 0; j + k <= W; k++)
            {
                DP[i][j][k] = (DP[i][j][k] + (j + 2)*(j + 1)/2*DP[i - 1][j + 2][k])%MOD;
                DP[i][j][k] = (DP[i][j][k] + (k + 1)*DP[i - 1][j][k + 1])%MOD;
                DP[i][j][k] = (DP[i][j][k] + (j + 1)*DP[i - 1][j + 1][k - 1])%MOD;
                DP[i][j][k] = (DP[i][j][k] + DP[i - 1][j][k])%MOD;
                // if (k == l) printf("DP[%d][%d][%d][%d] = %lld\n", i, j, k, l, DP[i][j][k][l]);
                if (i == H) Ans = (Ans + DP[i][j][k]*E[k])%MOD;
            }
        }
    }
    printf("%lld", (Ans + MOD - 1)%MOD);
}

Compilation message

tents.cpp: In function 'int main()':
tents.cpp:12:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &H, &W);
     ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 1336 KB Output is correct
3 Correct 2 ms 1336 KB Output is correct
4 Correct 4 ms 2516 KB Output is correct
5 Correct 65 ms 38656 KB Output is correct
6 Correct 64 ms 49028 KB Output is correct
7 Correct 73 ms 49028 KB Output is correct
8 Correct 46 ms 49028 KB Output is correct
9 Correct 3 ms 49028 KB Output is correct
10 Correct 129 ms 97436 KB Output is correct
11 Correct 14 ms 97436 KB Output is correct
12 Correct 389 ms 216640 KB Output is correct

Subtask #2
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 1336 KB Output is correct
3 Correct 2 ms 1336 KB Output is correct
4 Correct 4 ms 2516 KB Output is correct
5 Correct 65 ms 38656 KB Output is correct
6 Correct 64 ms 49028 KB Output is correct
7 Correct 73 ms 49028 KB Output is correct
8 Correct 46 ms 49028 KB Output is correct
9 Correct 3 ms 49028 KB Output is correct
10 Correct 129 ms 97436 KB Output is correct
11 Correct 14 ms 97436 KB Output is correct
12 Correct 389 ms 216640 KB Output is correct
13 Incorrect 33 ms 216640 KB Output isn't correct
14 Halted 0 ms 0 KB -