#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define x first
#define y second
using namespace std;
const int inf = 1e18 + 10;
const int nmax = 100;
int n, m;
char mat[nmax][nmax];
int comb[nmax][nmax];
static int add(int a, int b) {
if(a > inf - b)
return inf;
return a + b;
}
static vector<pii> move(vector<pii> initial) {
vector<pii> sol;
sort(initial.begin(), initial.end());
auto insert = [&](int x, int y) {
if(x >= n || y >= m)
return;
sol.push_back({x, y});
};
for(auto [a, b] : initial)
insert(a, b + 1);
int a, b;
tie(a, b) = initial.back();
insert(a + 1, b);
return sol;
}
static void solve(vector<pii> poz, string s, int k) {
sort(poz.begin(), poz.end(), [&](pii a, pii b) {return mat[a.x][a.y] < mat[b.x][b.y];});
if(poz.size() == 1 && poz.back() == pii{n - 1, m - 1}) {
cout << s << mat[n - 1][m - 1] << '\n';
exit(0);
}
char last = 0;
int sum = 0;
vector<pii> curr;
for(auto [a, b] : poz) {
if(last != mat[a][b]) {
if(sum >= k)
solve(move(curr), s + last, k);
k -= sum;
last = mat[a][b];
sum = 0;
curr.resize(0);
}
sum = add(sum, comb[n - a + m - b - 2][n - a - 1]);
curr.push_back({a, b});
}
solve(move(curr), s + last, k);
}
signed main() {
for(int i = 0; i < nmax; i++) {
comb[i][0] = comb[i][i] = 1;
for(int j = 1; j < i; j++)
comb[i][j] = add(comb[i - 1][j], comb[i - 1][j - 1]);
}
cin >> n >> m;
//cout << n << ' ' << m << '\n';
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
cin >> mat[i][j];
}
//cout << i << ' ' << n << '\n';
}
int k;
cin >> k;
vector<pii> v;
v.push_back({0,0});
solve(v, "", k);
}
Compilation message
kthpath.cpp: In function 'std::vector<std::pair<long long int, long long int> > move(std::vector<std::pair<long long int, long long int> >)':
kthpath.cpp:28:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
28 | for(auto [a, b] : initial)
| ^
kthpath.cpp: In function 'void solve(std::vector<std::pair<long long int, long long int> >, std::string, long long int)':
kthpath.cpp:45:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
45 | for(auto [a, b] : poz) {
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
