Submission #869315

#	Time	Username	Problem	Language	Result	Execution time	Memory
869315		12345678	Tents (JOI18_tents)	C++17	100 / 100	200 ms	212408 KiB

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 / 48
• Subtask 2: 52 / 52