Submission #1303797

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303797		domi	K-th path (IZhO11_kthpath)	C++20	100 / 100	3 ms	580 KiB

kthpath

#include <bits/stdc++.h>

#define int long long
#define fi first
#define se second

#define sz(a) (int)((a).size())
#define all(a) (a).begin(), (a).end()

#define lsb(x) (x & (-x))
#define vi vector<int>
#define YES { cout << "Yes" << endl; return; }
#define NO { cout << "No" << endl; return; }

using ll = long long;
using pii = std::pair<int, int>;

const int NMAX = 30;

using namespace std;

char a[NMAX + 5][NMAX + 5];
int dp[NMAX + 5][NMAX + 5][2], n, m, k;

int solve(string& sol) {
    fill(&dp[0][0][0], &dp[0][0][0] + (NMAX + 5) * (NMAX + 5) * 2, 0LL);

    dp[1][1][0] = 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            for (int lower = 0; lower < 2; ++lower) {
                if (i + 1 <= n) {
                    int new_lower = (lower | (a[i + 1][j] < sol[i + j - 1]));
                    if (!(new_lower == 0 && a[i + 1][j] > sol[i + j - 1]))
                        dp[i + 1][j][new_lower] += dp[i][j][lower];
                }

                if (j + 1 <= m) {
                    int new_lower = (lower | (a[i][j + 1] < sol[i + j - 1]));
                    if (!(new_lower == 0 && a[i][j + 1] > sol[i + j - 1]))
                        dp[i][j + 1][new_lower] += dp[i][j][lower];
                }
            }
        }
    }

    return dp[n][m][0] + dp[n][m][1];
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> m;

    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            cin >> a[i][j];

    cin >> k;
    string ans(n + m - 1, 'z');
    ans[0] = a[1][1];
    for (int i = 2; i <= n + m - 1; ++i) {
        int lo = 0, hi = 25, best = 0;

        while (lo <= hi) {
            auto mid = (lo + hi) >> 1;
            ans[i - 1] = static_cast<char>(mid + 'a');

            if (solve(ans) >= k) {
                best = mid;
                hi = mid - 1;
            }
            else
                lo = mid + 1;
        }

        ans[i - 1] = static_cast<char>(best + 'a');
    }

    cout << ans << '\n';
    return 0;
}

• Subtask 1: 100 / 100