| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 220308 |
2020-04-07T16:21:55 Z |
MKopchev |
Tents (JOI18_tents) |
C++14 |
|
222 ms |
35968 KB |
#include<bits/stdc++.h>
using namespace std;
const int nmax=3e3+5,mod=1e9+7,fourth=(mod+1)/4;
int dp[nmax][nmax];
int h,w;
int rec(int row,int free)
{
if(row>h)return 1;
if(dp[row][free]!=-1)return dp[row][free];
int ret=rec(row+1,free);//do not place
//place one
//on new and alone
if(free)ret=(ret+4LL*(free)*rec(row+1,free-1))%mod;
//on old(force with some other)
if(free&&row<h)ret=(ret+1LL*free*(h-row)%mod*rec(row+2,free-1))%mod;
//place two
if(free>=2)ret=(ret+1LL*free*(free-1)/2*rec(row+1,free-2))%mod;
dp[row][free]=ret;
return ret;
}
int main()
{
memset(dp,-1,sizeof(dp));
scanf("%i%i",&h,&w);
int output=rec(1,w);
output=(output+mod-1)%mod;
printf("%i\n",output);
return 0;
}
Compilation message
tents.cpp: In function 'int main()':
tents.cpp:32:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i%i",&h,&w);
~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
35712 KB |
Output is correct |
| 2 |
Correct |
23 ms |
35712 KB |
Output is correct |
| 3 |
Correct |
23 ms |
35712 KB |
Output is correct |
| 4 |
Correct |
23 ms |
35712 KB |
Output is correct |
| 5 |
Correct |
23 ms |
35712 KB |
Output is correct |
| 6 |
Correct |
23 ms |
35712 KB |
Output is correct |
| 7 |
Correct |
24 ms |
35712 KB |
Output is correct |
| 8 |
Correct |
24 ms |
35704 KB |
Output is correct |
| 9 |
Correct |
23 ms |
35712 KB |
Output is correct |
| 10 |
Correct |
24 ms |
35712 KB |
Output is correct |
| 11 |
Correct |
23 ms |
35712 KB |
Output is correct |
| 12 |
Correct |
25 ms |
35712 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
35712 KB |
Output is correct |
| 2 |
Correct |
23 ms |
35712 KB |
Output is correct |
| 3 |
Correct |
23 ms |
35712 KB |
Output is correct |
| 4 |
Correct |
23 ms |
35712 KB |
Output is correct |
| 5 |
Correct |
23 ms |
35712 KB |
Output is correct |
| 6 |
Correct |
23 ms |
35712 KB |
Output is correct |
| 7 |
Correct |
24 ms |
35712 KB |
Output is correct |
| 8 |
Correct |
24 ms |
35704 KB |
Output is correct |
| 9 |
Correct |
23 ms |
35712 KB |
Output is correct |
| 10 |
Correct |
24 ms |
35712 KB |
Output is correct |
| 11 |
Correct |
23 ms |
35712 KB |
Output is correct |
| 12 |
Correct |
25 ms |
35712 KB |
Output is correct |
| 13 |
Correct |
23 ms |
35712 KB |
Output is correct |
| 14 |
Correct |
23 ms |
35840 KB |
Output is correct |
| 15 |
Correct |
140 ms |
35832 KB |
Output is correct |
| 16 |
Correct |
25 ms |
35712 KB |
Output is correct |
| 17 |
Correct |
35 ms |
35712 KB |
Output is correct |
| 18 |
Correct |
47 ms |
35712 KB |
Output is correct |
| 19 |
Correct |
142 ms |
35936 KB |
Output is correct |
| 20 |
Correct |
132 ms |
35960 KB |
Output is correct |
| 21 |
Correct |
84 ms |
35840 KB |
Output is correct |
| 22 |
Correct |
86 ms |
35872 KB |
Output is correct |
| 23 |
Correct |
65 ms |
35968 KB |
Output is correct |
| 24 |
Correct |
212 ms |
35940 KB |
Output is correct |
| 25 |
Correct |
146 ms |
35840 KB |
Output is correct |
| 26 |
Correct |
187 ms |
35840 KB |
Output is correct |
| 27 |
Correct |
222 ms |
35960 KB |
Output is correct |
