Submission #1109813

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

kthpath

#include "bits/stdc++.h"

using namespace std;

void solve() {
    int n, m;
    cin >> n >> m;
    vector<string> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<vector<long long>> dp(n, vector<long long> (m));
    for (int i = n - 1; i >= 0; i--) {
        for (int j = m - 1; j >= 0; j--) {
            if (i == n - 1 && j == m - 1) {
                dp[i][j] = 1;
            } else {
                if (i + 1 < n) {
                    dp[i][j] += dp[i + 1][j];
                }
                if (j + 1 < m) {
                    dp[i][j] += dp[i][j + 1];
                }
            }
        }
    }
    long long k;
    cin >> k;
    vector<vector<long long>> tmp(n, vector<long long> (m));
    tmp[0][0] = 1;
    for (int s = 0; s <= n + m - 2; s++) {
        vector<pair<int, int>> pos;
        for (int i = 0; i < n; i++) {
            int j = s - i;
            if (j >= 0 && j < m && tmp[i][j]) {
                pos.push_back({i, j});
            }
        }
        cout << a[pos[0].first][pos[0].second];
        if (s == n + m - 2) {
            break;
        }
        vector<long long> cnt(26);
        for (auto [x, y] : pos) {
            if (x + 1 < n) {
                cnt[a[x + 1][y] - 'a'] += tmp[x][y] * dp[x + 1][y];
            }
            if (y + 1 < m) {
                cnt[a[x][y + 1] - 'a'] += tmp[x][y] * dp[x][y + 1];
            }
        }
        int ch = 0;
        while (cnt[ch] < k) {
            k -= cnt[ch];
            ch++;
        }
        for (auto [x, y] : pos) {
            if (x + 1 < n && a[x + 1][y] - 'a' == ch) {
                tmp[x + 1][y] += tmp[x][y];
            }
            if (y + 1 < m && a[x][y + 1] - 'a' == ch) {
                tmp[x][y + 1] += tmp[x][y];
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
//    cin >> t;
    while (t--) {
        solve();
    }
}

• Subtask 1: 100 / 100