#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;
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++)
{
for(auto [x,y]:v[ch])
{
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;
}
Compilation message
kthpath.cpp: In function 'int main()':
kthpath.cpp:51:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
51 | for(auto [x,y]:v[ch])
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
