oj.uz

Submission #523272

# Submission time Handle Problem Language Result Execution time Memory
523272 2022-02-07T09:54:00 Z RaresFelix K-th path (IZhO11_kthpath) C++17
100 / 100
 1 ms 332 KB 
#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.0 / 100.0

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