oj.uz

Submission #1109813

# Submission time Handle Problem Language Result Execution time Memory
1109813 2024-11-07T17:06:22 Z Kirill22 K-th path (IZhO11_kthpath) C++17
100 / 100
 1 ms 504 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 504 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 464 KB Output is correct
11 Correct 1 ms 504 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 1 ms 336 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 1 ms 336 KB Output is correct