Submission #230946

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
230946	2020-05-12T06:19:37 Z	AlexLuchianov	Tents (JOI18_tents)	C++14	100 / 100	225 ms	31992 KB

tents

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cassert>

using namespace std;

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 3000;
int const modulo = 1000000007;
int dp[1 + nmax][1 + nmax];

int extract(int i, int j){
  if(i < 0 || j < 0)
    return 0;
  else if(i == 0 || j == 0)
    return 1;
  else if(dp[i][j] == 0){
    dp[i][j] = (extract(i - 1, j) +
               1LL * extract(i - 1, j - 1) * (j * 4) +
               1LL * extract(i - 1, j - 2) * ((j * (j - 1)) / 2) +
               1LL * extract(i - 2, j - 1) * j * (i - 1)) % modulo;
   }
  return dp[i][j];
}
int main()
{
  int n, m;
  cin >> n >> m;
  cout << (modulo + extract(n, m) - 1) % modulo;
  return 0;
}

Subtask #1

48.0 / 48.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	4 ms	384 KB	Output is correct
3	Correct	5 ms	512 KB	Output is correct
4	Correct	5 ms	1152 KB	Output is correct
5	Correct	5 ms	640 KB	Output is correct
6	Correct	6 ms	1408 KB	Output is correct
7	Correct	5 ms	768 KB	Output is correct
8	Correct	5 ms	1408 KB	Output is correct
9	Correct	5 ms	768 KB	Output is correct
10	Correct	6 ms	1664 KB	Output is correct
11	Correct	5 ms	384 KB	Output is correct
12	Correct	7 ms	1792 KB	Output is correct

Subtask #2

52.0 / 52.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	4 ms	384 KB	Output is correct
3	Correct	5 ms	512 KB	Output is correct
4	Correct	5 ms	1152 KB	Output is correct
5	Correct	5 ms	640 KB	Output is correct
6	Correct	6 ms	1408 KB	Output is correct
7	Correct	5 ms	768 KB	Output is correct
8	Correct	5 ms	1408 KB	Output is correct
9	Correct	5 ms	768 KB	Output is correct
10	Correct	6 ms	1664 KB	Output is correct
11	Correct	5 ms	384 KB	Output is correct
12	Correct	7 ms	1792 KB	Output is correct
13	Correct	5 ms	384 KB	Output is correct
14	Correct	11 ms	9728 KB	Output is correct
15	Correct	142 ms	29176 KB	Output is correct
16	Correct	6 ms	1408 KB	Output is correct
17	Correct	19 ms	4992 KB	Output is correct
18	Correct	37 ms	9336 KB	Output is correct
19	Correct	160 ms	30972 KB	Output is correct
20	Correct	135 ms	25464 KB	Output is correct
21	Correct	76 ms	16120 KB	Output is correct
22	Correct	80 ms	19960 KB	Output is correct
23	Correct	58 ms	19576 KB	Output is correct
24	Correct	221 ms	31992 KB	Output is correct
25	Correct	176 ms	27128 KB	Output is correct
26	Correct	181 ms	29816 KB	Output is correct
27	Correct	225 ms	31080 KB	Output is correct