#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
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 = 0; i < n; ++i)cin >> a[i];
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];
}
long long k;
cin >> k;
string ans = "";
vector<pair<int, int>> v,cur;
v.push_back({ 0,0 });
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[0].first][v[0].second];
}
for (int j = 0; j < v.size(); ++j) {
if (v[j].first + 1 < n) {
C[a[v[j].first + 1][v[j].second]-'a'] += dp[v[j].first + 1][v[j].second];
}
if (v[j].second + 1 < m) {
C[a[v[j].first][v[j].second + 1]-'a'] += dp[v[j].first][v[j].second + 1];
}
}
for (int j = 0; j < 26; ++j) {
if (C[j] < k) {
k -= C[j];
}
else {
ans += char(j + 'a');
cur.clear();
for (int c = 0; c < v.size(); ++c) {
if (v[c].first + 1 < n&&a[v[c].first + 1][v[c].second] - 'a' == j) {
cur.push_back({ v[c].first + 1,v[c].second });
}
if (v[c].second + 1 < m&&a[v[c].first][v[c].second + 1] - 'a' == j) {
cur.push_back({ v[c].first,v[c].second + 1 });
}
}
v = cur;
break;
}
}
}
cout << ans << endl;
return 0;
}
Compilation message
kthpath.cpp: In function 'int main()':
kthpath.cpp:31:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < v.size(); ++j) {
^
kthpath.cpp:46:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int c = 0; c < v.size(); ++c) {
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
492 KB |
Output is correct |
| 3 |
Correct |
2 ms |
580 KB |
Output is correct |
| 4 |
Correct |
2 ms |
816 KB |
Output is correct |
| 5 |
Correct |
2 ms |
816 KB |
Output is correct |
| 6 |
Correct |
2 ms |
816 KB |
Output is correct |
| 7 |
Correct |
2 ms |
816 KB |
Output is correct |
| 8 |
Correct |
2 ms |
984 KB |
Output is correct |
| 9 |
Correct |
1 ms |
984 KB |
Output is correct |
| 10 |
Runtime error |
728 ms |
262144 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 11 |
Halted |
0 ms |
0 KB |
- |
