| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1126753 | Tsagana | K-th path (IZhO11_kthpath) | C11 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define all(x) x.begin(), x.end()
#define lnl long long
#define pq priority_queue
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pp pop_back
#define F first
#define S second
using namespace std;
int dp[31][31];
string a[31];
void solve () {
for (int i = 1; i < 31; i++)
for (int j = 1; j < 31; j++)
dp[i][j] = dp[i-1][j] + dp[i][j-1], dp[1][1] = 1;
int n, m; cin >> n >> m;
for (int i = 0; i < n; i++) cin >> a[i];
int k; 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;
}
int main() {IOS solve(); return 0;}