# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
752260 | aykhn | K-th path (IZhO11_kthpath) | C++14 | 1 ms | 212 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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[26];
int used[50][50];
int sum[26];
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));
int cnt = 1;
while (cnt < n + m)
{
int s = 0;
int ind = -1;
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 && !used[x + 1][y])
{
nw.pb(mpr(x + 1, y));
used[x + 1][y] = 1;
sum[v[x + 1][y] - 'a'] += dp[x + 1][y];
}
if (y + 1 <= m && !used[x][y + 1])
{
nw.pb(mpr(x, y + 1));
used[x][y + 1] = 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;
cnt++;
}
cout << ans << endl;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |