Submission #525524

#TimeUsernameProblemLanguageResultExecution timeMemory
525524sidonK-th path (IZhO11_kthpath)C++17
100 / 100
1 ms332 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int Z = 35; int n, m, k, dp[Z][Z]; string a[Z]; int32_t main() { ios::sync_with_stdio(0), cin.tie(0); for(int i = 1; i < Z; ++i) for(int j = 1; j < Z; ++j) dp[i][j] = dp[i-1][j] + dp[i][j-1], dp[1][1] = 1; cin >> n >> m; for(int i = 0; i < n; ++i) cin >> a[i]; cin >> k; string ans(n+m-1, a[0][0]); map<array<int, 2>, int> cur, nxt; cur[{0, 0}] = 1; for(int i = 0; i < n+m-1; ++i) { map<char, int> sum; for(auto &[j, cnt] : cur) { auto [x, y] = j; sum[a[x][y]] += dp[n-x][m-y] * cnt; } for(auto &[c, s] : sum) { ans[i] = c; if(s < k) k -= s; else break; } for(auto &[j, cnt] : cur) { auto [x, y] = j; if(a[x][y] == ans[i]) { if(x+1 != n) nxt[{x+1, y}] += cnt; if(y+1 != m) nxt[{x, y+1}] += cnt; } } cur = nxt; nxt.clear(); } cout << ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...