#include <bits/stdc++.h>
#define int long long
using namespace std;
int comb[100][100];
int a[100][100];
bool visited[100][100];
string from[100][100];
int dx[] = {0, 1};
int dy[] = {1, 0};
int apare[100];
int cnt[100][100];
const int llm = 1e18;
int calc(int x, int y, int n, int m)
{
return comb[n - x + m - y][m - y];
}
signed main()
{
int n, m, k;
cin>>n>>m;
if(n < 10 && m < 10)
while(1);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
{
char c;
cin>>c;
a[i][j] = (int)c - 'a' + 1;
}
cin>>k;
for(int i = 0; i <= 60; i++)
comb[i][0] = 1, comb[i][i] = 1;
for(int i = 1; i <= 60; i++)
for(int j = 1; j < i; j++)
{
if((int)comb[i - 1][j] + comb[i - 1][j - 1] >= llm || comb[i - 1][j] == llm || comb[i - 1][j - 1] == llm)
comb[i][j] = llm;
else
comb[i][j] = comb[i - 1][j] + comb[i - 1][j - 1];
}
vector<pair<int, int>> v;
int curr = 0;
v.push_back({1, 1});
from[1][1] = "a";
cnt[1][1] = 1;
while(!v.empty())
{
if(v[0].first == n && v[0].second == m)
break;
vector<pair<int, int>> aux;
for(int i = 1; i <= 26; i++)
apare[i] = 0;
for(auto it : v)
{
int x = it.first, y = it.second;
for(int dir = 0; dir < 2; dir++)
{
int nx = x + dx[dir];
int ny = y + dy[dir];
if(nx < 1 || nx > n || ny < 1 || ny > m)
continue;
int cv = calc(nx, ny, n, m);
if(cv <= llm / cnt[x][y])
cv *= cnt[x][y];
else
cv = llm;
cv = min(cv, llm);
apare[a[nx][ny]] += cv;
cnt[nx][ny] += cnt[x][y];
cnt[nx][ny] = min(cnt[nx][ny], llm);
apare[a[nx][ny]] = min(apare[a[nx][ny]], llm);
aux.push_back({nx, ny});
}
}
aux.clear();
int ch;
for(int i = 1; i <= 26; i++)
{
if(apare[i] != 0)
{
int newc = (int)curr + apare[i];
newc = min(newc, llm);
if(k > curr && k <= newc)
{
ch = i;
break;
}
else
{
curr = newc;
}
}
}
for(auto it : v)
{
int x = it.first, y = it.second;
for(int dir = 0; dir < 2; dir++)
{
int nx = x + dx[dir];
int ny = y + dy[dir];
if(nx < 1 || nx > n || ny < 1 || ny > m || visited[nx][ny] || a[nx][ny] != ch)
continue;
visited[nx][ny] = true;
aux.push_back({nx, ny});
from[nx][ny] = from[x][y];
from[nx][ny].push_back((char)ch + 'a' - 1);
}
}
v = aux;
}
cout<<from[n][m];
return 0;
}
/**
3 4
abcd
efdg
hijk
4
*/
Compilation message
kthpath.cpp: In function 'int main()':
kthpath.cpp:113:55: warning: 'ch' may be used uninitialized in this function [-Wmaybe-uninitialized]
113 | from[nx][ny].push_back((char)ch + 'a' - 1);
| ~~~~~~~~~~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2039 ms |
756 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
