Submission #445702

#	Time	Username	Problem	Language	Result	Execution time	Memory
445702		iulia13	K-th path (IZhO11_kthpath)	C++14	100 / 100	2 ms	296 KiB

kthpath

#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 (stderr)

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 / 100