oj.uz

Submission #445702

# Submission time Handle Problem Language Result Execution time Memory
445702 2021-07-19T10:10:40 Z iulia13 K-th path (IZhO11_kthpath) C++14
100 / 100
 2 ms 296 KB 
#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define f first
#define s second
const int N = 50;
char a[N][N];
ll dp[N][N];
char ans[N];
int n, m;
ll nrways(int x, int y)
{
    if (ans[x + y - 1] && ans[x + y - 1] != a[x][y])
        return 0;
    if (dp[x][y] != -1)
        return dp[x][y];
    dp[x][y] = 0;
    if (x < n)
        dp[x][y] += nrways(x + 1, y);
    if (y < m)
        dp[x][y] += nrways(x, y + 1);
    return dp[x][y];
}
int main()
{
   /// freopen ("kthpath.in", "r", stdin);
  ///  freopen ("kthpath.out", "w", stdout);
    int i, j;
    cin >> n >> m;
    for (i = 1; i <= n; i++)
        cin >> a[i] + 1;
    ll k;
    cin >> k;
    ans[1] = a[1][1];
    for (int h = 2; h < n + m; h++)
        for (int l = 0; l < 26; l++)
        {
            ans[h] = l + 'a';
            memset(dp, -1, sizeof dp);
            dp[n][m] = 1;
            if (nrways(1, 1) >= k)
                break;
            k -= nrways(1, 1);
        }
    for (i = 1; i < n + m; i++)
        cout << ans[i];
    return 0;
}

Compilation message

kthpath.cpp: In function 'int main()':
kthpath.cpp:32:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |         cin >> a[i] + 1;
      |                ~~~~~^~~
kthpath.cpp:29:12: warning: unused variable 'j' [-Wunused-variable]
   29 |     int i, j;
      |            ^

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 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 1 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 1 ms 204 KB Output is correct
10 Correct 2 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 2 ms 296 KB Output is correct
14 Correct 2 ms 204 KB Output is correct
15 Correct 2 ms 204 KB Output is correct
16 Correct 2 ms 204 KB Output is correct
17 Correct 2 ms 204 KB Output is correct
18 Correct 2 ms 204 KB Output is correct
19 Correct 2 ms 204 KB Output is correct
20 Correct 2 ms 288 KB Output is correct