Submission #998391

#	Time	Username	Problem	Language	Result	Execution time	Memory
998391		ag_1204	Tents (JOI18_tents)	C++17	100 / 100	73 ms	70828 KiB

tents

#include<bits/stdc++.h>
using namespace std;
#define ll long long int

int main(){
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    ll mod=1e9+7;
    ll h,w; cin>>h>>w;
    ll grid[h+1][w+1];
    for (ll i=0;i<=h;i++) {
        for (ll j=0;j<=w;j++) {
            if (i==0 || j==0) {
                grid[i][j]=1;
            } else {
                grid[i][j]=0;
            }
        }
    }
    for (ll i=1;i<=h;i++) {
        for (ll j=1;j<=w;j++) {
            grid[i][j]=grid[i-1][j];
    		if (j>1) {
    		    ll k1=j*(j-1);
    		    k1/=2;
    		    k1*=grid[i-1][j-2];
    		    grid[i][j]+=k1;
    		}
    		if (i>1) {
			    ll k2=j*(i-1);
			    k2*=grid[i-2][j-1];
			    grid[i][j]+=k2;
			}
    		ll k=4*j;
    		k*=grid[i-1][j-1];
			grid[i][j]+=k;
			grid[i][j]%=mod;
        }
    }
    grid[h][w]--;
    cout<<grid[h][w]<<endl;
	return 0;
}

• Subtask 1: 48 / 48
• Subtask 2: 52 / 52