| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 253392 |
2020-07-27T21:40:56 Z |
ChrisT |
Tents (JOI18_tents) |
C++17 |
|
381 ms |
36092 KB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using ld = long double;
#define all(x) (x).begin(),(x).end()
#define ree(x) ((x-1)*(x-2)/2)
const int MN = 5e5+3, MK = 1001, MOD = 1e9+7;
mt19937_64 rnd = mt19937_64(chrono::steady_clock::now().time_since_epoch().count());
int dp[3005][3005];
void uadd (int &a, int b) {
a += b;
if (a >= MOD) a -= MOD;
}
int recur (int h, int w) {
if(h<0||w<0) return 0;
if (h<1||w<1) return 1;
if (h==1&&w==1) return 5;
if (~dp[h][w]) return dp[h][w];
int ret = 0;
uadd(ret,4LL*recur(h-1,w-1)%MOD);
uadd(ret,(w-1)*1LL*recur(h-1,w-2)%MOD);
uadd(ret,(h-1)*1LL*recur(h-2,w-1)%MOD);
uadd(ret,recur(h-1,w));
uadd(ret,(w-1)*4LL%MOD*recur(h-1,w-1)%MOD);
uadd(ret,(w-1)*1LL*(h-1)%MOD*recur(h-2,w-1)%MOD);
uadd(ret,(w-1)*1LL*(w-2)/2%MOD*recur(h-1,w-2)%MOD);
return dp[h][w] = ret;
}
int main() {
memset(dp,-1,sizeof dp);
int h,w;
scanf ("%d %d",&h,&w);
int ret = recur(h,w)-1;
if (ret < 0)ret += MOD;
printf ("%d\n",ret);
return 0;
}
Compilation message
tents.cpp: In function 'int main()':
tents.cpp:35:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d %d",&h,&w);
~~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
35712 KB |
Output is correct |
| 2 |
Correct |
19 ms |
35712 KB |
Output is correct |
| 3 |
Correct |
21 ms |
35704 KB |
Output is correct |
| 4 |
Correct |
19 ms |
35712 KB |
Output is correct |
| 5 |
Correct |
19 ms |
35712 KB |
Output is correct |
| 6 |
Correct |
19 ms |
35712 KB |
Output is correct |
| 7 |
Correct |
19 ms |
35712 KB |
Output is correct |
| 8 |
Correct |
19 ms |
35712 KB |
Output is correct |
| 9 |
Correct |
19 ms |
35712 KB |
Output is correct |
| 10 |
Correct |
20 ms |
35712 KB |
Output is correct |
| 11 |
Correct |
19 ms |
35712 KB |
Output is correct |
| 12 |
Correct |
21 ms |
35712 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
35712 KB |
Output is correct |
| 2 |
Correct |
19 ms |
35712 KB |
Output is correct |
| 3 |
Correct |
21 ms |
35704 KB |
Output is correct |
| 4 |
Correct |
19 ms |
35712 KB |
Output is correct |
| 5 |
Correct |
19 ms |
35712 KB |
Output is correct |
| 6 |
Correct |
19 ms |
35712 KB |
Output is correct |
| 7 |
Correct |
19 ms |
35712 KB |
Output is correct |
| 8 |
Correct |
19 ms |
35712 KB |
Output is correct |
| 9 |
Correct |
19 ms |
35712 KB |
Output is correct |
| 10 |
Correct |
20 ms |
35712 KB |
Output is correct |
| 11 |
Correct |
19 ms |
35712 KB |
Output is correct |
| 12 |
Correct |
21 ms |
35712 KB |
Output is correct |
| 13 |
Correct |
18 ms |
35712 KB |
Output is correct |
| 14 |
Correct |
18 ms |
35832 KB |
Output is correct |
| 15 |
Correct |
270 ms |
35968 KB |
Output is correct |
| 16 |
Correct |
21 ms |
35712 KB |
Output is correct |
| 17 |
Correct |
36 ms |
35712 KB |
Output is correct |
| 18 |
Correct |
72 ms |
35712 KB |
Output is correct |
| 19 |
Correct |
293 ms |
35968 KB |
Output is correct |
| 20 |
Correct |
253 ms |
35960 KB |
Output is correct |
| 21 |
Correct |
132 ms |
35832 KB |
Output is correct |
| 22 |
Correct |
152 ms |
35840 KB |
Output is correct |
| 23 |
Correct |
120 ms |
35968 KB |
Output is correct |
| 24 |
Correct |
381 ms |
36092 KB |
Output is correct |
| 25 |
Correct |
270 ms |
35960 KB |
Output is correct |
| 26 |
Correct |
317 ms |
35972 KB |
Output is correct |
| 27 |
Correct |
345 ms |
35968 KB |
Output is correct |
