Submission #523272

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

kthpath

#include <bits/stdc++.h>

#define MN 37

using namespace std;

using ll = long long;

ll n, m, k;
char A[MN][MN];

string sol;
ll DP[MN][MN][3];// < = >
ll nr() {
    ///raspunde in O(n * m)
    DP[n][m][0] = (sol[n + m - 2] > A[n][m]);
    DP[n][m][1] = (sol[n + m - 2] == A[n][m]);
    DP[n][m][2] = (sol[n + m - 2] < A[n][m]);
    for (ll i = n; i >= 1; --i) {
        for (ll j = m - (i == n); j >= 1; --j) {
            if (sol[i + j - 2] > A[i][j])
                DP[i][j][0] = DP[i + 1][j][0] + DP[i + 1][j][1] + DP[i + 1][j][2] +
                              DP[i][j + 1][0] + DP[i][j + 1][1] + DP[i][j + 1][2],
                DP[i][j][1] = 0,
                DP[i][j][2] = 0;
            else if (sol[i + j - 2] < A[i][j])
                DP[i][j][0] = 0,
                DP[i][j][1] = 0,
                DP[i][j][2] = DP[i + 1][j][0] + DP[i + 1][j][1] + DP[i + 1][j][2] +
                              DP[i][j + 1][0] + DP[i][j + 1][1] + DP[i][j + 1][2];
            else
                DP[i][j][0] = DP[i + 1][j][0] + DP[i][j + 1][0],
                DP[i][j][1] = DP[i + 1][j][1] + DP[i][j + 1][1],
                DP[i][j][2] = DP[i + 1][j][2] + DP[i][j + 1][2];
        }
    }
    return DP[1][1][0] + DP[1][1][1];
}

ll mi_greedy(ll p) {
    ///daca ar fi sa completez cu 'a' restul string-ului, care ar fi rez?
    for (ll i = p; i < n + m - 1; ++i) sol[i] = 'a';
    return nr();
}

ll ma_greedy(ll p) {
    ///daca ar fi sa completez cu 'z' restul string-ului, care ar fi rez?
    for (ll i = p; i < n + m - 1; ++i) sol[i] = 'z';
    return nr();
}

void gen(int p) {
    if (p == n + m) return;
    char st = 'a', dr = 'z', mij;
    while (st < dr) {
        mij = (st + dr) / 2;
        sol[p] = mij;
        if (ma_greedy(p + 1) < k) st = mij + 1;
        else dr = mij;
    }
    sol[p] = st;
    gen(p + 1);
}

int main() {
    cin >> n >> m;
    sol.assign(n + m - 1, 'a');
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            cin >> A[i][j];
    ///caut primul string cu nr(s) >= k
    cin >> k;
    gen(0);
    cout << sol << "\n";
}

• Subtask 1: 100 / 100