#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
const int maxN=101;
const ll inf=2e18;
int n,m;
ll dp[maxN+1][maxN+1][maxN+1],k;
char c[maxN+1][maxN+1];
vector<pii> v[26];
string s;
bool check(int i,int j,int x,int y)
{
if(i+1==x&&j==y)
{
return true;
}
if(i==x&&j+1==y)
{
return true;
}
return false;
}
int main()
{
//freopen("","r",stdin);
//freopen("","w",stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=n;i>=1;i--)
{
for(int j=m;j>=1;j--)
{
cin>>c[i][j];
v[c[i][j]-'a'].push_back({i,j});
}
}
cin>>k;
dp[0][1][1]=1;
for(int st=1;st<=n+m-2;st++)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
dp[st][i][j]+=(dp[st-1][i-1][j]+dp[st-1][i][j-1]);
}
}
}
s="";
s+=c[n][m];
for(int st=n+m-3;st>=1;st--)
{
ll res=0,cur=0;
for(int ch=0;ch<26;ch++)
{
if(st==n+m-3)
{
for(auto [x,y]:v[ch])
{
if(check(x,y,n,m))
{
res+=dp[st][x][y];
}
}
}
else
{
for(auto [x,y]:v[ch])
{
for(auto [i,j]:v[s[s.size()-1]-'a'])
{
if(check(x,y,i,j))
{
res+=dp[st][x][y];
}
}
}
}
if(res>=k)
{
s+=(char)(ch+'a');
k-=cur;
//cout<<st<<" "<<ch<<'\n';
break;
}
cur=res;
}
}
s+=c[1][1];
//reverse(s.begin(),s.end());
cout<<s;
}
/*2 3
abc
def
3*/
Compilation message
kthpath.cpp: In function 'int main()':
kthpath.cpp:65:26: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
65 | for(auto [x,y]:v[ch])
| ^
kthpath.cpp:75:26: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
75 | for(auto [x,y]:v[ch])
| ^
kthpath.cpp:77:30: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
77 | for(auto [i,j]:v[s[s.size()-1]-'a'])
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
