# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
525521 | sidon | K-th path (IZhO11_kthpath) | C++17 | 364 ms | 262148 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]);
vector<array<int, 2>> cur = {{0, 0}}, nxt;
for(int i = 0; i < n+m-1; ++i) {
map<char, int> sum;
for(auto &[x, y] : cur)
sum[a[x][y]] += dp[n-x][m-y];
for(auto &[c, s] : sum) {
ans[i] = c;
if(s < k) k -= s;
else break;
}
for(auto &[x, y] : cur) if(a[x][y] == ans[i]) {
if(x+1 != n) nxt.push_back({x+1, y});
if(y+1 != m) nxt.push_back({x, y+1});
}
cur = nxt;
nxt.clear();
}
cout << ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |