Submission #874462

#TimeUsernameProblemLanguageResultExecution timeMemory
874462The_SamuraiK-th path (IZhO11_kthpath)C++17
0 / 100
0 ms356 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); 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] >= k) { ch = c; break; } sum += dp[x][y]; } // cout << time << ' ' << v.size() << ' ' << k << endl; k -= sum; assert(ch != '#'); ans[time] = ch; set<tuple<char, int, int>> nw; for (auto [c, x, y]: v) { if (c != ch) continue; if (x + 1 < n) nw.emplace(a[x + 1][y], x + 1, y); if (y + 1 < m) nw.emplace(a[x][y + 1], x, y + 1); } 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...