#include <bits/stdc++.h>
// author: aykhn
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define TC int t; cin >> t; while (t--) _();
#define OPT ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define all(v) v.begin(), v.end()
#define mpr make_pair
#define eb emplace_back
#define pb push_back
#define ts to_string
#define fi first
#define se second
#define ins insert
#define int ll
#define inf 0x3F3F3F3F
#define infll 0x3F3F3F3F3F3F3F3FLL
#define bpc __builtin_popcount
int n, m, k;
int ways;
vector<string> v;
vector<pii> rn;
vector<int> a[50];
int used[50][50];
int sum[50];
signed main()
{
OPT;
cin >> n >> m;
v.resize(n + 1, "$");
vector<vector<int>> dp(n + 1, vector<int> (m + 1, 1));
for (int i = 1; i <= n; i++)
{
string tmp;
cin >> tmp;
v[i] += tmp;
}
cin >> k;
for (int i = n - 1; i >= 1; i--)
{
for (int j = m - 1; j >= 1; j--)
{
dp[i][j] = dp[i + 1][j] + dp[i][j + 1];
}
}
sum[v[1][1] - 'a'] = dp[1][1];
string ans = "";
rn.pb(mpr(1, 1));
while (rn.size())
{
int s = 0;
int ind = 0;
for (int i = 0; i < 26; i++)
{
s += sum[i];
if (s >= k)
{
ind = i;
break;
}
}
ans.pb(ind + 'a');
int sz = rn.size();
vector<pii> nw;
for (int i = 0; i < sz; i++)
{
sum[v[rn[i].fi][rn[i].se] - 'a'] -= dp[rn[i].fi][rn[i].se];
if (v[rn[i].fi][rn[i].se] - 'a' == ind)
{
int x = rn[i].fi;
int y = rn[i].se;
if (x + 1 <= n)
{
nw.pb(mpr(x + 1, y));
sum[v[x + 1][y] - 'a'] += dp[x + 1][y];
}
if (y + 1 <= m)
{
nw.pb(mpr(x, y + 1));
sum[v[x][y + 1] - 'a'] += dp[x][y + 1];
}
}
else if (v[rn[i].fi][rn[i].se] - 'a' < ind)
{
k -= dp[rn[i].fi][rn[i].se];
}
}
rn = nw;
if (rn[0].fi == n && rn[0].se == m) break;
}
cout << ans << v[n][m] << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
