| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 543189 | Lobo | Tropical Garden (IOI11_garden) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
const int maxn = -1;
void solve() {
cin >> n >> K >> H;
for(int i = 1; i <= K; i++) {
int x; cin >> x;
mark[x] = i;
}
for(int i = 1; i <= n+1; i++) {
dp1[i][i-1] = 1;
}
for(int sz = 1; sz <= n; sz++) {
for(int l = 1; l <= n; l++) {
int r = l+sz-1;
if(r > n) return;
pair<int,int> mn = mp(0,0);
for(int i = l; i <= r; i++) {
mn = min(mn, mp(mark[i],i));
}
if(mn.fr != 0) {
int i = mn.sc;
int ans1 = 1;
if(i-1 >= l) ans1 = dp1[l][i-1];
int ans2 = 1;
if(i+1 <= r) ans2 = dp1[i+1][r];
dp1[l][r] = (ans1*ans2)%mod;
}
else {
for(int i = l; i <= r; i++) {
int ans1 = 1;
if(i-1 >= l) ans1 = dp1[l][i-1];
int ans2 = 1;
if(i+1 <= r) ans2 = dp1[i+1][r];
dp1[l][r]+= (ans1*ans2)%mod;
dp1[l][r]%= mod;
}
}
}
}
for(int h = 0; h <= H; h++) {
for(int sz = 1; sz <= n; i++) {
for(int l = 1; l <= n; l++) {
if(l == r) {
if(h == 0) dp[l][r][h] = 1;
else dp[l][r][h] = 0;
continue;
}
if(h == 0) {
dp[l][r][h] = 0;
}
int r = l+sz-1;
pair<int,int> mn = mp(0,0);
for(int i = l; i <= r; i++) {
mn = min(mn, mp(mark[i],i));
}
if(mn.fr != 0) {
int i = mn.sc;
dp[l][r][h]+= dp[l][i-1][h-1]
}
}
}
}
}
int32_t main() {
ios::sync_with_stdio(false); cin.tie(0);
freopen("in.in", "r", stdin);
// freopen("out.out", "w", stdout);
int tt = 1;
// cin >> tt;
while(tt--) solve();
}