Submission #41185

#TimeUsernameProblemLanguageResultExecution timeMemory
41185alenam0161K-th path (IZhO11_kthpath)C++14
0 / 100
728 ms262144 KiB
#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 (stderr)

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 timeMemoryGrader output
Fetching results...