| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 996150 |
2024-06-10T08:17:57 Z |
LOLOLO |
Zapina (COCI20_zapina) |
C++14 |
|
366 ms |
2648 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define f first
#define s second
#define pb push_back
#define ep emplace
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define uniquev(v) sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define mem(f,x) memset(f , x , sizeof(f))
#define sz(x) (ll)(x).size()
#define __lcm(a, b) (1ll * ((a) / __gcd((a), (b))) * (b))
#define mxx *max_element
#define mnn *min_element
#define cntbit(x) __builtin_popcountll(x)
#define len(x) (int)(x.length())
ll mod = 1e9 + 7;
const int N = 355;
int dp[N][N][2];
ll c[N][N];
ll cal(int x, int y) {
if (x > y)
return 0;
if (x == 0)
return 1;
if (c[x][y] != -1)
return c[x][y];
return c[x][y] = (cal(x, y - 1) + cal(x - 1, y - 1)) % mod;
}
ll dq(int id, int ss, int is) {
if (id == 0) {
return is && (ss == 0);
}
if (dp[id][ss][is] != -1) {
return dp[id][ss][is];
}
ll ans = 0;
for (int j = 0; j <= ss; j++) {
ll cc = dq(id - 1, ss - j, (j == id) || is) * cal(j, ss) % mod;
ans += cc;
ans %= mod;
}
return dp[id][ss][is] = ans;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
mem(c, -1);
mem(dp, -1);
int n;
cin >> n;
cout << dq(n, n, 0) << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2396 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 8 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 9 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 10 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 11 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 12 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 13 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 14 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 15 |
Correct |
1 ms |
2648 KB |
Output is correct |
| 16 |
Correct |
1 ms |
2396 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 8 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 9 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 10 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 11 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 12 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 13 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 14 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 15 |
Correct |
1 ms |
2648 KB |
Output is correct |
| 16 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 17 |
Correct |
178 ms |
2436 KB |
Output is correct |
| 18 |
Correct |
3 ms |
2392 KB |
Output is correct |
| 19 |
Correct |
39 ms |
2392 KB |
Output is correct |
| 20 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 21 |
Correct |
232 ms |
2440 KB |
Output is correct |
| 22 |
Correct |
25 ms |
2392 KB |
Output is correct |
| 23 |
Correct |
3 ms |
2428 KB |
Output is correct |
| 24 |
Correct |
49 ms |
2396 KB |
Output is correct |
| 25 |
Correct |
33 ms |
2420 KB |
Output is correct |
| 26 |
Correct |
66 ms |
2396 KB |
Output is correct |
| 27 |
Correct |
332 ms |
2396 KB |
Output is correct |
| 28 |
Correct |
335 ms |
2396 KB |
Output is correct |
| 29 |
Correct |
331 ms |
2644 KB |
Output is correct |
| 30 |
Correct |
334 ms |
2396 KB |
Output is correct |
| 31 |
Correct |
341 ms |
2456 KB |
Output is correct |
| 32 |
Correct |
342 ms |
2396 KB |
Output is correct |
| 33 |
Correct |
345 ms |
2396 KB |
Output is correct |
| 34 |
Correct |
345 ms |
2396 KB |
Output is correct |
| 35 |
Correct |
348 ms |
2396 KB |
Output is correct |
| 36 |
Correct |
352 ms |
2456 KB |
Output is correct |
| 37 |
Correct |
366 ms |
2396 KB |
Output is correct |
