Submission #346448

#	Time	Username	Problem	Language	Result	Execution time	Memory
346448		CaroLinda	Tents (JOI18_tents)	C++14	100 / 100	135 ms	71020 KiB

tents

#include <bits/stdc++.h>

#define ll long long

const int MAX = 3010 ;
const ll MOD = 1e9+7 ;

using namespace std ;

int N , M ;
ll dp[MAX][MAX] ;

int main()
{
	scanf("%d %d", &N, &M ) ;

	for(int i = 0 ; i <= max(N,M) ; i++ ) dp[0][i] = dp[i][0] = 1 ;

	for(int i= 1 ; i <= N ; i++ )
	{
		ll bin = (ll)i * (i-1)  ;
		bin = (bin>>1LL ) % MOD ;

		ll c = (4*i) % MOD ;

		for(int j = 1 , aux = 0 ; j <= M ; j++, aux += i )
		{
			if( aux >= MOD ) aux -= MOD ;

			ll &ptr = dp[i][j] ;

			ptr = dp[i][j-1] ;
			ptr += ( c * dp[i-1][j-1] ) % MOD ;

			if( ptr >= MOD ) ptr -= MOD ;

			if(i >= 2 )
			{
				ptr += ( bin * dp[i-2][j-1] ) % MOD ;
				if( ptr >= MOD ) ptr -= MOD ;
			}

			if( j >= 2 )
			{
				ptr += ( aux * dp[i-1][j-2] ) % MOD ;
				if( ptr >= MOD ) ptr -= MOD ;
			}

		}

	}


	ll ans = dp[N][M] - 1LL ;

	if( ans < 0 ) ans += MOD ;

	printf("%lld\n", ans ) ;

}

Compilation message (stderr)

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

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