#include <bits/stdc++.h>
#define N 35
using namespace std;
int n,m;
long long k;
char arr[N][N];
long long ways[N][N];
vector<pair<int,int>> dx = {{1,0},{0,1}};
bool ck(int a,int b){
return a > 0 && a <= n && b > 0 && b <= m;
}
void solve(){
cin >> n >> m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin >> arr[i][j];
}
}
ways[n][m] = 1;
for(int i=n;i>=1;i--){
for(int j=m;j>=1;j--){
if(i == n && j == m)continue;
ways[i][j] = ways[i+1][j] + ways[i][j+1];
}
}
cin >> k;
cout << arr[1][1];
vector<pair<int,int>> now;
now.push_back({1,1});
map<pair<int,int>,int> mp;
mp[{1,1}] = 1;
while(now[0].first != n || now[0].second != m){
set<pair<int,int>> nw;
for(auto u:now){
for(auto v:dx){
if(ck(u.first + v.first,u.second + v.second)){
nw.insert({u.first + v.first,u.second + v.second});
mp[{u.first + v.first,u.second + v.second}]++;
}
}
}
vector<long long> cnt(26);
for(auto u:nw){
cnt[arr[u.first][u.second] - 'a'] += ways[u.first][u.second] * mp[u];
cnt[arr[u.first][u.second] - 'a'] = min(k,cnt[arr[u.first][u.second] - 'a']);
}
int num = 0;
for(;num<26;num++){
if(cnt[num] < k){
k -= cnt[num];
}
else{
cout << (char)(num + 'a');
break;
}
}
now.clear();
for(auto u:nw){
if(arr[u.first][u.second] - 'a' == num){
now.push_back(u);
}
}
}
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#ifdef Local
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
int t=1;
//cin>>t;
while(t--){
solve();
}
#ifdef Local
cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
#endif
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Execution timed out |
2087 ms |
204 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
