oj.uz

Submission #337793

# Submission time Handle Problem Language Result Execution time Memory
337793 2020-12-21T16:20:13 Z er888kh Tents (JOI18_tents) C++17
100 / 100
 366 ms 71296 KB 
#include <bits/stdc++.h>

using namespace std;

#define ALL(iter) (iter).begin(),(iter).end()

typedef int64_t s64;
typedef pair<int, int> pii;
typedef pair<s64, s64> pll;

#define F first
#define S second

#define MAXN 3003

s64 mem[MAXN][MAXN];

const int md = 1e9 + 7;

inline s64 binom(int n){
	return ((n * 1LL * (n-1)) >> 1) % md;
}

s64 dp(int h, int w){
	if(h < 0 || w < 0){
		return 0;
	}
	if(h == 0 || w == 0){
		return 1;
	}
	if(mem[h][w] != -1){
		return mem[h][w];
	}
	s64 sm = dp(h-1, w); //do nothing
	sm += binom(w) * dp(h-1, w-2);
	sm %= md;
	sm += 4 * w * dp(h-1, w-1);
	sm %= md;
	sm += (h-1) * w * dp(h-2, w-1);
	sm %= md;
	return mem[h][w] = sm;
}

int main(){
	for(int i = 0; i < MAXN; i++){
		fill(mem[i], mem[i]+MAXN, -1);
	}
	int h, w;
	scanf("%d%d", &h, &w);
	printf("%lld\n", (dp(h, w) - 1 + md) % md);
	return 0;
}

Compilation message

tents.cpp: In function 'int main()':
tents.cpp:50:13: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type 's64' {aka 'long int'} [-Wformat=]
   50 |  printf("%lld\n", (dp(h, w) - 1 + md) % md);
      |          ~~~^     ~~~~~~~~~~~~~~~~~~~~~~~~
      |             |                         |
      |             long long int             s64 {aka long int}
      |          %ld
tents.cpp:49:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   49 |  scanf("%d%d", &h, &w);
      |  ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 70892 KB Output is correct
2 Correct 35 ms 70892 KB Output is correct
3 Correct 34 ms 70892 KB Output is correct
4 Correct 36 ms 70892 KB Output is correct
5 Correct 35 ms 70892 KB Output is correct
6 Correct 36 ms 71020 KB Output is correct
7 Correct 35 ms 70912 KB Output is correct
8 Correct 36 ms 70892 KB Output is correct
9 Correct 34 ms 70892 KB Output is correct
10 Correct 36 ms 70892 KB Output is correct
11 Correct 34 ms 70912 KB Output is correct
12 Correct 42 ms 70892 KB Output is correct

Subtask #2
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 70892 KB Output is correct
2 Correct 35 ms 70892 KB Output is correct
3 Correct 34 ms 70892 KB Output is correct
4 Correct 36 ms 70892 KB Output is correct
5 Correct 35 ms 70892 KB Output is correct
6 Correct 36 ms 71020 KB Output is correct
7 Correct 35 ms 70912 KB Output is correct
8 Correct 36 ms 70892 KB Output is correct
9 Correct 34 ms 70892 KB Output is correct
10 Correct 36 ms 70892 KB Output is correct
11 Correct 34 ms 70912 KB Output is correct
12 Correct 42 ms 70892 KB Output is correct
13 Correct 37 ms 70892 KB Output is correct
14 Correct 35 ms 71148 KB Output is correct
15 Correct 248 ms 71148 KB Output is correct
16 Correct 39 ms 70892 KB Output is correct
17 Correct 55 ms 71020 KB Output is correct
18 Correct 79 ms 71020 KB Output is correct
19 Correct 276 ms 71276 KB Output is correct
20 Correct 220 ms 71188 KB Output is correct
21 Correct 137 ms 71020 KB Output is correct
22 Correct 145 ms 71148 KB Output is correct
23 Correct 101 ms 71296 KB Output is correct
24 Correct 366 ms 71148 KB Output is correct
25 Correct 277 ms 71276 KB Output is correct
26 Correct 313 ms 71276 KB Output is correct
27 Correct 347 ms 71276 KB Output is correct