Submission #874466

#TimeUsernameProblemLanguageResultExecution timeMemory
874466The_SamuraiK-th path (IZhO11_kthpath)C++17
100 / 100
1 ms452 KiB
// #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] * cnt[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 timeMemoryGrader output
Fetching results...