oj.uz

Submission #963163

# Submission time Handle Problem Language Result Execution time Memory
963163 2024-04-14T15:58:58 Z biank K-th path (IZhO11_kthpath) C++17
0 / 100
 1 ms 348 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 30;

using ll = __int128;

ll dp[MAX_N][MAX_N];
char g[MAX_N][MAX_N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int n, m;
    cin >> n >> m;
    
    dp[n - 1][m - 1] = 1;
    for (int i = n - 1; i >= 0; i--) {
        for (int j = m - 1; j >= 0; j--) {
            if (i != n - 1) dp[i][j] += dp[i + 1][j];
            if (j != m - 1) dp[i][j] += dp[i][j + 1];
        }
    }
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> g[i][j];
        }
    }
    long long k;
    cin >> k;
    
    string ans = "";
    int i = 0, j = 0;
    while (i != n - 1 && j != m - 1) {
        ans += g[i][j];
        if (g[i + 1][j] < g[i][j + 1]) {
            if (k <= dp[i + 1][j]) i++;
            else k -= dp[i + 1][j], j++;
        } else {
            if (k <= dp[i][j + 1]) j++;
            else k -= dp[i][j + 1], i++;
        }
    }
    while (i != n - 1) ans += g[i][j], i++;
    while (j != m) ans += g[i][j], j++;
    cout << ans << '\n';
    
    return 0;
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -