답안 #1003931

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1003931	2024-06-20T20:17:47 Z	AdamGS	Tents (JOI18_tents)	C++17	100 / 100	65 ms	70996 KB

tents

#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const ll MOD=1e9+7;
const int LIM=3e3+7;
ll dp[LIM][LIM];
int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  int h, w;
  cin >> h >> w;
  rep(i, h+1) dp[i][0]=1;
  rep(i, w+1) dp[0][i]=1;
  for(int n=1; n<=h; ++n) for(int m=1; m<=w; ++m) {
    ll a=dp[n-1][m];
    ll b=(dp[n-1][m-1]*4*m)%MOD;
    ll c=0;
    if(m>=2) c=(dp[n-1][m-2]*((m*(m-1)/2)%MOD))%MOD;
    ll d=0;
    if(n>=2) d=(dp[n-2][m-1]*((m*(n-1))%MOD))%MOD;
    dp[n][m]=(a+b+c+d)%MOD;
  }
  ll ans=(dp[h][w]-1+MOD)%MOD;
  cout << ans << '\n';
}

Subtask #1

48.0 / 48.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	1 ms	6492 KB	Output is correct
5	Correct	1 ms	2396 KB	Output is correct
6	Correct	1 ms	6648 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	1 ms	6492 KB	Output is correct
9	Correct	1 ms	4444 KB	Output is correct
10	Correct	1 ms	8540 KB	Output is correct
11	Correct	1 ms	2396 KB	Output is correct
12	Correct	2 ms	8540 KB	Output is correct

Subtask #2

52.0 / 52.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	1 ms	6492 KB	Output is correct
5	Correct	1 ms	2396 KB	Output is correct
6	Correct	1 ms	6648 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	1 ms	6492 KB	Output is correct
9	Correct	1 ms	4444 KB	Output is correct
10	Correct	1 ms	8540 KB	Output is correct
11	Correct	1 ms	2396 KB	Output is correct
12	Correct	2 ms	8540 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	5 ms	55876 KB	Output is correct
15	Correct	45 ms	66140 KB	Output is correct
16	Correct	4 ms	6744 KB	Output is correct
17	Correct	11 ms	16988 KB	Output is correct
18	Correct	14 ms	29276 KB	Output is correct
19	Correct	51 ms	70236 KB	Output is correct
20	Correct	40 ms	57948 KB	Output is correct
21	Correct	28 ms	39512 KB	Output is correct
22	Correct	25 ms	51804 KB	Output is correct
23	Correct	17 ms	70492 KB	Output is correct
24	Correct	64 ms	70996 KB	Output is correct
25	Correct	51 ms	62184 KB	Output is correct
26	Correct	53 ms	68184 KB	Output is correct
27	Correct	65 ms	70232 KB	Output is correct