oj.uz

Submission #683333

# Submission time Handle Problem Language Result Execution time Memory
683333 2023-01-18T07:57:37 Z KiriLL1ca K-th path (IZhO11_kthpath) C++17
100 / 100
 1 ms 340 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 320 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 316 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct