| # |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
| 56308 |
2018-07-11T04:17:53 Z |
윤교준(#1600) |
Tents (JOI18_tents) |
C++11 |
|
2000 ms |
33268 KB |
#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[(sz(V)-2)])
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define clv(V) (V).clear()
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
const int MOD = 1000000007;
const int MAXH = 3005;
const int MAXW = 3005;
int dp[MAXH][MAXW];
int H, W;
int f(int H, int W) {
int &ret = dp[H][W];
if(0 <= ret) return ret;
ret = 1;
for(int k = 1; k <= H; k++)
ret = (ll(f(H-k, W-1)) * W % MOD * 4 + ret) % MOD;
for(int k = 1; k < H; k++)
ret = (ll(H-k) * f(H-k-1, W-1) % MOD * W + ret) % MOD;
for(int k = 1; k <= H; k++)
ret = (ll(W) * (W-1) / 2 % MOD * f(H-k, W-2) + ret) % MOD;
return ret;
}
int main() {
cin >> H >> W;
for(int i = 0; i <= H; i++) dp[i][0] = 1;
for(int i = 0; i <= W; i++) dp[0][i] = 1;
for(int i = 1; i <= H; i++)
fill(dp[i]+1, dp[i]+W+1, -1);
cout << (f(H, W) - 1) << endl;
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
560 KB |
Output is correct |
| 4 |
Correct |
3 ms |
1200 KB |
Output is correct |
| 5 |
Correct |
5 ms |
1200 KB |
Output is correct |
| 6 |
Correct |
57 ms |
1388 KB |
Output is correct |
| 7 |
Correct |
10 ms |
1388 KB |
Output is correct |
| 8 |
Correct |
42 ms |
1664 KB |
Output is correct |
| 9 |
Correct |
3 ms |
1664 KB |
Output is correct |
| 10 |
Correct |
107 ms |
1796 KB |
Output is correct |
| 11 |
Correct |
2 ms |
1796 KB |
Output is correct |
| 12 |
Correct |
187 ms |
2132 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
560 KB |
Output is correct |
| 4 |
Correct |
3 ms |
1200 KB |
Output is correct |
| 5 |
Correct |
5 ms |
1200 KB |
Output is correct |
| 6 |
Correct |
57 ms |
1388 KB |
Output is correct |
| 7 |
Correct |
10 ms |
1388 KB |
Output is correct |
| 8 |
Correct |
42 ms |
1664 KB |
Output is correct |
| 9 |
Correct |
3 ms |
1664 KB |
Output is correct |
| 10 |
Correct |
107 ms |
1796 KB |
Output is correct |
| 11 |
Correct |
2 ms |
1796 KB |
Output is correct |
| 12 |
Correct |
187 ms |
2132 KB |
Output is correct |
| 13 |
Correct |
2 ms |
2132 KB |
Output is correct |
| 14 |
Correct |
85 ms |
9940 KB |
Output is correct |
| 15 |
Execution timed out |
2049 ms |
33268 KB |
Time limit exceeded |
| 16 |
Halted |
0 ms |
0 KB |
- |
