#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <functional>
int x, y;
int64_t k;
char arr[30][31];
int64_t count_solutions(const std::string& tgt) {
std::vector<std::vector<std::vector<int64_t>>> dp(x,std::vector<std::vector<int64_t>>(y,std::vector<int64_t>(2,-1)));
const std::function<int64_t(int,int,int)> sol = [&](int i, int j, int tight) {
if (i==x-1&&j==y-1) {
return static_cast<int64_t>(1);
}
if (dp[i][j][tight]!=-1) {
return dp[i][j][tight];
}
int64_t ret = 0;
if (i+1<x &&
((tight) ? arr[i+1][j]<=tgt[i+1+j] : 1)) {
ret += sol(i+1,j,tight&(arr[i+1][j]==tgt[i+1+j]));
}
if (j+1<y &&
((tight) ? arr[i][j+1]<=tgt[i+j+1] : 1)) {
ret += sol(i,j+1,tight&(arr[i][j+1]==tgt[i+j+1]));
}
return dp[i][j][tight] = ret;
};
return sol(0,0,1);
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);
std::cin >> x >> y;
for (int i = 0; i < x; i++) {
std::cin >> arr[i];
}
std::cin >> k;
std::string tgt(x+y-1,'z');
tgt[0] = arr[0][0];
tgt[x+y-2] = arr[x-1][y-1];
for (int i = 1; i < x+y-2; i++) {
while (1) {
std::string tmp = tgt;
tmp[i] -= 1;
//std::cout << tmp << " " << count_solutions(tmp) << "\n";
if (tmp[i]=='a'||count_solutions(tmp)<k) {
break;
}
tgt[i] -= 1;
}
}
std::cout << tgt << "\n";
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
452 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
468 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
