Submission #822407

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
822407	2023-08-12T03:08:43 Z	irmuun	Tents (JOI18_tents)	C++17	100 / 100	152 ms	70792 KB

tents

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

const ll mod=1e9+7;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll h,w;
    cin>>h>>w;
    ll dp[h+1][w+1];
    for(ll i=0;i<=h;i++){
        for(ll j=0;j<=w;j++){
            if(i==0||j==0){
                dp[i][j]=1;
                continue;
            }
            dp[i][j]=(dp[i][j-1]+dp[i-1][j-1]*4*i)%mod;
            if(i>=2){
                dp[i][j]+=dp[i-2][j-1]*i*(i-1)/2;
                dp[i][j]%=mod;
            }
            if(j>=2){
                dp[i][j]+=dp[i-1][j-2]*i*(j-1);
                dp[i][j]%=mod;
            }
        }
    }
    cout<<(dp[h][w]-1+mod)%mod;
}

Subtask #1

48.0 / 48.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	320 KB	Output is correct
2	Correct	1 ms	320 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	320 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	468 KB	Output is correct
7	Correct	1 ms	468 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	2 ms	596 KB	Output is correct
11	Correct	5 ms	368 KB	Output is correct
12	Correct	3 ms	980 KB	Output is correct

Subtask #2

52.0 / 52.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	320 KB	Output is correct
2	Correct	1 ms	320 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	320 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	468 KB	Output is correct
7	Correct	1 ms	468 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	2 ms	596 KB	Output is correct
11	Correct	5 ms	368 KB	Output is correct
12	Correct	3 ms	980 KB	Output is correct
13	Correct	0 ms	340 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	97 ms	43996 KB	Output is correct
16	Correct	7 ms	3136 KB	Output is correct
17	Correct	22 ms	10088 KB	Output is correct
18	Correct	27 ms	12452 KB	Output is correct
19	Correct	111 ms	51260 KB	Output is correct
20	Correct	91 ms	41092 KB	Output is correct
21	Correct	61 ms	27164 KB	Output is correct
22	Correct	60 ms	26780 KB	Output is correct
23	Correct	32 ms	14932 KB	Output is correct
24	Correct	152 ms	70792 KB	Output is correct
25	Correct	115 ms	52540 KB	Output is correct
26	Correct	133 ms	60244 KB	Output is correct
27	Correct	145 ms	68044 KB	Output is correct