Submission #683333

#	Time	Username	Problem	Language	Result	Execution time	Memory
683333		KiriLL1ca	K-th path (IZhO11_kthpath)	C++17	100 / 100	1 ms	340 KiB

kthpath

#include <bits/stdc++.h>
#define vec vector
#define forn(i, s, f) for (int i = s; i <= f; ++i)
#define pb push_back
#define sz(x) (int)((int)(x).size())
#define endl '\n'

using namespace std;

typedef long long ll;
template <typename T> inline bool umin (T &a, const T &b) { if (a > b) { a = b; return 1; } return 0; }
template <typename T> inline bool umax (T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }

typedef pair <int, int> pii;

inline void solve () {
        int n, m; cin >> n >> m;
        vector <string> a (n);
        for (auto &i : a) cin >> i;
        ll k; cin >> k;
        vector <vector <ll>> from_end (n, vector <ll> (m));
        from_end[n - 1][m - 1] = 1;
        for (int i = n - 1; ~i; --i) {
                for (int j = m - 1; ~j; --j) {
                        if (i != n - 1) from_end[i][j] += from_end[i + 1][j];
                        if (j != m - 1) from_end[i][j] += from_end[i][j + 1];
                }
        }

        vector <vector <ll>> ways (n, vector <ll> (m));
        string res; res.pb(a[0][0]); ways[0][0] = 1;

        for (int len = 1; len < n + m - 1; ++len) {
                vector <ll> sym (26);
                for (int s = max(0, len - m); s < min(n, len); ++s) {
                        int ss = len - s - 1;
                        if (s + 1 < n) sym[a[s + 1][ss] - 'a'] += from_end[s + 1][ss] * ways[s][ss];
                        if (ss + 1 < m) sym[a[s][ss + 1] - 'a'] += from_end[s][ss + 1] * ways[s][ss];
                }
                int s = 0;
                while (s < 25) {
                        if (k > sym[s]) k -= sym[s++];
                        else break;
                }
                res.pb((char)(s + 'a'));
                for (int s = max(0, len - m); s < min(n, len); ++s) {
                        int ss = len - s - 1;
                        if (s + 1 < n && a[s + 1][ss] == res.back()) ways[s + 1][ss] += ways[s][ss];
                        if (ss + 1 < m && a[s][ss + 1] == res.back()) ways[s][ss + 1] += ways[s][ss];
                }
        }
        cout << res << endl;
}

signed main() {
        ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
        #ifdef LOCAL
                freopen("input.txt", "r", stdin);
                freopen("output.txt", "w", stdout);
        #else
                
        #endif
        int t = 1; // cin >> t;
        while (t--) solve();
        return 0;
}

• Subtask 1: 100 / 100