Submission #413603

# Submission time Handle Problem Language Result Execution time Memory
413603 2021-05-29T04:27:42 Z jamezzz Tents (JOI18_tents) C++14
100 / 100
325 ms 71236 KB
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#include <ext/rope>
using namespace __gnu_cxx;

typedef tree<long long, null_type, less<long long>,
rb_tree_tag, tree_order_statistics_node_update> pbds;
//less_equal for identical elements

//#define DEBUG

#ifdef DEBUG
#define debug(...) printf(__VA_ARGS__);
#else
#define debug(...)
#endif
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb emplace_back
#define sz(x) (int)x.size()
#define mnto(x,y) x=min(x,(__typeof__(x))y)
#define mxto(x,y) x=max(x,(__typeof__(x))y)
#define INF 1023456789
#define LINF 1023456789123456789
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<pll> vll;

#define mod 1000000007
ll m[3005][3005];

ll dp(int h,int w){
	if(h<0||w<0)return 0;
	if(h==0||w==0)return 1;
	if(m[h][w]!=-1)return m[h][w];
	if(h==1)return 4*w+1+w*(w-1)/2;
	return m[h][w]=(dp(h-1,w)+4*w*dp(h-1,w-1)+w*(w-1)/2*dp(h-1,w-2)+w*(h-1)*dp(h-2,w-1))%mod;
}

int main(){
	int h,w;sf("%d%d",&h,&w);
	memset(m,-1,sizeof m);
	pf("%lld\n",(dp(h,w)-1+mod)%mod);
}

Compilation message

tents.cpp: In function 'int main()':
tents.cpp:53:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |  int h,w;sf("%d%d",&h,&w);
      |            ^
# Verdict Execution time Memory Grader output
1 Correct 30 ms 70860 KB Output is correct
2 Correct 31 ms 70960 KB Output is correct
3 Correct 30 ms 70948 KB Output is correct
4 Correct 30 ms 70944 KB Output is correct
5 Correct 30 ms 70976 KB Output is correct
6 Correct 31 ms 70944 KB Output is correct
7 Correct 30 ms 70876 KB Output is correct
8 Correct 34 ms 70992 KB Output is correct
9 Correct 30 ms 70948 KB Output is correct
10 Correct 31 ms 70972 KB Output is correct
11 Correct 30 ms 70860 KB Output is correct
12 Correct 33 ms 71000 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 30 ms 70860 KB Output is correct
2 Correct 31 ms 70960 KB Output is correct
3 Correct 30 ms 70948 KB Output is correct
4 Correct 30 ms 70944 KB Output is correct
5 Correct 30 ms 70976 KB Output is correct
6 Correct 31 ms 70944 KB Output is correct
7 Correct 30 ms 70876 KB Output is correct
8 Correct 34 ms 70992 KB Output is correct
9 Correct 30 ms 70948 KB Output is correct
10 Correct 31 ms 70972 KB Output is correct
11 Correct 30 ms 70860 KB Output is correct
12 Correct 33 ms 71000 KB Output is correct
13 Correct 30 ms 70924 KB Output is correct
14 Correct 31 ms 71132 KB Output is correct
15 Correct 202 ms 71164 KB Output is correct
16 Correct 32 ms 70988 KB Output is correct
17 Correct 48 ms 71004 KB Output is correct
18 Correct 70 ms 71044 KB Output is correct
19 Correct 244 ms 71236 KB Output is correct
20 Correct 195 ms 71132 KB Output is correct
21 Correct 130 ms 71080 KB Output is correct
22 Correct 148 ms 71116 KB Output is correct
23 Correct 82 ms 71116 KB Output is correct
24 Correct 325 ms 71192 KB Output is correct
25 Correct 239 ms 71160 KB Output is correct
26 Correct 276 ms 71180 KB Output is correct
27 Correct 313 ms 71184 KB Output is correct