Submission #869315

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
869315	2023-11-04T03:02:12 Z	12345678	Tents (JOI18_tents)	C++17	100 / 100	200 ms	212408 KB

tents

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int mod=1e9+7, nx=3e3+5;
ll h, w, dp[nx][nx], qs[nx][nx], ans[nx][nx];

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>h>>w;
    for (int i=1; i<=h; i++)
    {
        for (int j=1; j<=w; j++)
        {
            dp[i][j]=((ans[i-1][j-1]+1)*4)%mod;
            dp[i][j]=(dp[i][j]+qs[i-1][j-1]*4*(j-1))%mod;
            if (j>=2)
            {
                dp[i][j]=(dp[i][j]+(j-1)*(ans[i-1][j-2]+1))%mod;
                dp[i][j]=(dp[i][j]+(j-1)*(j-2)/2*qs[i-1][j-2])%mod;
            }
            if (i>=2) 
            {
                dp[i][j]=(dp[i][j]+(i-1)*(ans[i-2][j-1]+1))%mod;
                dp[i][j]=(dp[i][j]+(j-1)*(i-1)*qs[i-2][j-1])%mod;
            }
            ans[i][j]=((ans[i-1][j]+ans[i][j-1]-ans[i-1][j-1]+dp[i][j])%mod+mod)%mod;
            qs[i][j]=(qs[i-1][j]+dp[i][j])%mod;
        }
    }
    cout<<ans[h][w];
}

Subtask #1

48.0 / 48.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	2396 KB	Output is correct
2	Correct	0 ms	2396 KB	Output is correct
3	Correct	1 ms	4700 KB	Output is correct
4	Correct	2 ms	13660 KB	Output is correct
5	Correct	2 ms	7260 KB	Output is correct
6	Correct	3 ms	15568 KB	Output is correct
7	Correct	2 ms	7452 KB	Output is correct
8	Correct	3 ms	17752 KB	Output is correct
9	Correct	2 ms	9304 KB	Output is correct
10	Correct	3 ms	20060 KB	Output is correct
11	Correct	1 ms	2652 KB	Output is correct
12	Correct	4 ms	20572 KB	Output is correct

Subtask #2

52.0 / 52.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	2396 KB	Output is correct
2	Correct	0 ms	2396 KB	Output is correct
3	Correct	1 ms	4700 KB	Output is correct
4	Correct	2 ms	13660 KB	Output is correct
5	Correct	2 ms	7260 KB	Output is correct
6	Correct	3 ms	15568 KB	Output is correct
7	Correct	2 ms	7452 KB	Output is correct
8	Correct	3 ms	17752 KB	Output is correct
9	Correct	2 ms	9304 KB	Output is correct
10	Correct	3 ms	20060 KB	Output is correct
11	Correct	1 ms	2652 KB	Output is correct
12	Correct	4 ms	20572 KB	Output is correct
13	Correct	1 ms	2396 KB	Output is correct
14	Correct	26 ms	120696 KB	Output is correct
15	Correct	131 ms	197072 KB	Output is correct
16	Correct	10 ms	21144 KB	Output is correct
17	Correct	28 ms	51284 KB	Output is correct
18	Correct	40 ms	79956 KB	Output is correct
19	Correct	175 ms	209528 KB	Output is correct
20	Correct	118 ms	173888 KB	Output is correct
21	Correct	78 ms	118908 KB	Output is correct
22	Correct	77 ms	150236 KB	Output is correct
23	Correct	56 ms	177304 KB	Output is correct
24	Correct	200 ms	212408 KB	Output is correct
25	Correct	150 ms	188628 KB	Output is correct
26	Correct	153 ms	205136 KB	Output is correct
27	Correct	172 ms	211632 KB	Output is correct