oj.uz

Submission #902547

# Submission time Handle Problem Language Result Execution time Memory
902547 2024-01-10T16:20:54 Z LOLOLO K-th path (IZhO11_kthpath) C++17
100 / 100
 2 ms 600 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define sz(x)   (int)(x).size()
#define len(x)  (int)(x).length()
#define cntbit(x)  builtin_popcnt(x)
#define f   first
#define s   second
#define pb  push_back
#define po(x)   (1 << (x))

const int N = 50;
char mat[N][N];
ull dp[N][N][2], num;
string s;
int n, m;

ll cal() {
    memset(dp, 0, sizeof(dp));
    if (mat[1][1] > s[0])
        return 0;

    if (mat[1][1] == s[0]) {
        dp[1][1][1] = 1;
    } else {
        dp[1][1][0] = 1;
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (i == 1 && j == 1)
                continue;

            int k = i + j - 2;
            if (s[k] == mat[i][j]) {
                dp[i][j][1] = dp[i - 1][j][1] + dp[i][j - 1][1];
                dp[i][j][0] = dp[i - 1][j][0] + dp[i][j - 1][0];
            } else {
                if (s[k] > mat[i][j]) {
                    dp[i][j][0] = dp[i - 1][j][1] + dp[i][j - 1][1] + dp[i][j - 1][0] + dp[i - 1][j][0];
                } else {
                    dp[i][j][0] = dp[i - 1][j][0] + dp[i][j - 1][0];
                }
            }

            dp[i][j][0] = min(num + 1, dp[i][j][0]);
            dp[i][j][1] = min(num + 1, dp[i][j][1]);
        }
    }

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

ll solve() {
    cin >> n >> m;

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

    for (int i = 1; i < n + m; i++)
        s += 'z';

    ll num1;
    cin >> num1;
    num = num1;

    for (int i = 0; i < len(s); i++) {
        char l = 'a', r = 'z', m;
        while (l <= r) {
            m = (l + r) / 2;
            char p = s[i];
            s[i] = m;
            //cout << cal() << " lmao\n";
            if (cal() >= num) {
                r = m - 1;
            } else {
                l = m + 1;
                s[i] = p;
            }
        }
    }

    cout << s << '\n';

    return 0;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    //cin >> t;

    while (t--) {
        solve();
        //cout << solve() << '\n';
    }

}

Compilation message

kthpath.cpp: In function 'll solve()':
kthpath.cpp:78:23: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'ull' {aka 'long long unsigned int'} [-Wsign-compare]
   78 |             if (cal() >= num) {
      |                 ~~~~~~^~~~~~

Subtask #1
100.0 / 100.0

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