Submission #41190

#TimeUsernameProblemLanguageResultExecution timeMemory
41190alenam0161K-th path (IZhO11_kthpath)C++14
0 / 100
1 ms484 KiB
#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <algorithm> #include <string> #include <map> using namespace std; const int N = 3e3 + 7; long long dp[N][N]; string a[N]; long long C[N]; int main() { //freopen("input.txt", "r", stdin); int n, m; cin >> n >> m; for (int i = n - 1; i >= 0; i--) for (int j = m - 1; j >= 0; j--) { if (i == n - 1 && j == m - 1)dp[i][j] = 1; else dp[i][j] = dp[i + 1][j] + dp[i][j + 1]; } for (int i = 0; i < n; ++i)cin >> a[i]; long long k; cin >> k; string ans = ""; map<pair<int, int>,long long> v,cur; v[{0, 0}] = 1; for (int i = 0; i < (n + m)-1; ++i) { for (int j = 0; j < 26; ++j)C[j] = 0; if (i == 0) { ans += a[v.begin()->first.first][v.begin()->first.second]; } for (auto to:v) { if (to.first.first + 1 < n) { C[a[to.first.first + 1][to.first.second]-'a'] += to.second*dp[to.first.second+ 1][to.first.second]; } if (to.first.second + 1 < m) { C[a[to.first.first][to.first.second + 1]-'a'] += dp[to.first.first][to.first.second + 1]; } } for (int j = 0; j < 26; ++j) { if (C[j] < k) { k -= C[j]; } else { ans += char(j + 'a'); cur.clear(); for (auto to:v) { if (to.first.first + 1 < n&&a[to.first.first + 1][to.first.second] - 'a' == j) { cur[{ to.first.first + 1,to.first.second }]+=to.second; } if (to.first.second + 1 < m&&a[to.first.first][to.first.second + 1] - 'a' == j) { cur[{ to.first.first,to.first.second + 1 }]+=to.second; } } v = cur; break; } } } cout << ans << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...