// #pragma GCC optimize("Ofast,O3")
// #pragma GCC target("avx,avx2")
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
void solve() {
int n, m;
cin >> n >> m;
vector<string> a(n);
for (string &s: a) cin >> s;
ll k;
cin >> k;
vector dp(n, vector(m, 0ll));
dp[n - 1][m - 1] = 1;
for (int i = n - 1; i >= 0; i--) {
for (int j = m - 1; j >= 0; j--) {
if (i + 1 < n) dp[i][j] += dp[i + 1][j];
if (j + 1 < m) dp[i][j] += dp[i][j + 1];
}
}
string ans(n + m - 1, '#');
set<tuple<char, int, int>> v; v.emplace(a[0][0], 0, 0);
vector cnt(n, vector(m, 0ll)); cnt[0][0] = 1;
for (int time = 0; time < n + m - 1; time++) {
ll sum = 0; char ch = '#';
for (auto [c, x, y]: v) {
if (sum + dp[x][y] * cnt[x][y] >= k) {
ch = c;
break;
}
sum += dp[x][y] * cnt[x][y];
}
assert(ch != '#');
sum = 0;
set<tuple<char, int, int>> nw;
for (auto [c, x, y]: v) {
if (c > ch) break;
if (c < ch) sum += dp[x][y];
else {
if (x + 1 < n) {
nw.emplace(a[x + 1][y], x + 1, y);
cnt[x + 1][y] += cnt[x][y];
}
if (y + 1 < m) {
nw.emplace(a[x][y + 1], x, y + 1);
cnt[x][y + 1] += cnt[x][y];
}
}
}
k -= sum;
ans[time] = ch;
v = nw;
}
cout << ans;
}
int main() {
cin.tie(0)->sync_with_stdio(false);
#ifdef sunnatov
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int q = 1;
// cin >> q;
while (q--) {
solve();
cout << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
600 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 5 |
Halted |
0 ms |
0 KB |
- |
