Submission #127552

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
127552	2019-07-09T14:50:03 Z	RockyB	Tents (JOI18_tents)	C++17	100 / 100	136 ms	35704 KB

tents

#include <bits/stdc++.h>
 
#define rep(a, b, c) for (int a = (b); (a) <= (c); a++)
#define per(a, b, c) for (int a = (b); (a) >= (c); a--)
 
#define nl '\n'
#define ioi exit(0);
 
const int mod = (int)1e9 + 7;
const int N = (int)1e4;
 
using namespace std;
 
void add(int &x, int y) {
  x += y;
  if (x >= mod) x -= mod;
}
int sum(int x, int y) {
  add(x, y);
  return x;
}
int n, m;
 
int dp[3005][3005];
int main() {
  #ifdef IOI
    freopen ("in.txt", "r", stdin);
    freopen ("slow.out", "w", stdout);
  #endif
  cin >> n >> m;
  /* memset(dp, -1, sizeof(dp));
  int ans = sum(calc(), -1);
  cout << ans << nl; */
  dp[0][m] = 1;
  rep(i, 0, n - 1) {
    rep(j, 0, m) {
      add(dp[i + 1][j], dp[i][j]);
      if (j > 0) {
        add(dp[i + 1][j - 1], dp[i][j] * 1ll * 4 * j % mod);
      	add(dp[i + 2][j - 1], dp[i][j] * 1ll * (n - i - 1) * j % mod);
      }
      if (j > 1) add(dp[i + 1][j - 2], dp[i][j] * 1ll * (j * (j - 1) / 2) % mod);
    }
  }
  int ans = -1;
  rep(i, 0, m) add(ans, dp[n][i]);
  if (ans < 0) ans += mod;
  cout << ans;
  ioi
}
 
/*
 
5116 0
3720 1
450 2
 
*/

Subtask #1

48.0 / 48.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	256 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	504 KB	Output is correct
4	Correct	3 ms	1144 KB	Output is correct
5	Correct	3 ms	632 KB	Output is correct
6	Correct	3 ms	1400 KB	Output is correct
7	Correct	3 ms	760 KB	Output is correct
8	Correct	3 ms	1400 KB	Output is correct
9	Correct	2 ms	760 KB	Output is correct
10	Correct	4 ms	1656 KB	Output is correct
11	Correct	2 ms	376 KB	Output is correct
12	Correct	5 ms	1912 KB	Output is correct

Subtask #2

52.0 / 52.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	256 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	504 KB	Output is correct
4	Correct	3 ms	1144 KB	Output is correct
5	Correct	3 ms	632 KB	Output is correct
6	Correct	3 ms	1400 KB	Output is correct
7	Correct	3 ms	760 KB	Output is correct
8	Correct	3 ms	1400 KB	Output is correct
9	Correct	2 ms	760 KB	Output is correct
10	Correct	4 ms	1656 KB	Output is correct
11	Correct	2 ms	376 KB	Output is correct
12	Correct	5 ms	1912 KB	Output is correct
13	Correct	2 ms	376 KB	Output is correct
14	Correct	13 ms	9592 KB	Output is correct
15	Correct	95 ms	32884 KB	Output is correct
16	Correct	8 ms	2680 KB	Output is correct
17	Correct	23 ms	8056 KB	Output is correct
18	Correct	30 ms	11000 KB	Output is correct
19	Correct	107 ms	34680 KB	Output is correct
20	Correct	86 ms	29052 KB	Output is correct
21	Correct	58 ms	19832 KB	Output is correct
22	Correct	61 ms	22264 KB	Output is correct
23	Correct	43 ms	19704 KB	Output is correct
24	Correct	136 ms	35704 KB	Output is correct
25	Correct	110 ms	30840 KB	Output is correct
26	Correct	117 ms	33528 KB	Output is correct
27	Correct	128 ms	34680 KB	Output is correct