# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
753801 | AliHasanli | K-th path (IZhO11_kthpath) | C++17 | 1 ms | 340 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;
#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 time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |