oj.uz

답안 #445694

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
445694 2021-07-19T09:41:05 Z iulia13 K번째 경로 (IZhO11_kthpath) C++14
0 / 100
 1 ms 204 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 ways[N][N];
int main()
{
    ///freopen ("kthpath.in", "r", stdin);
   /// freopen ("kthpath.out", "w", stdout);
    int n, m, i, j;
    cin >> n >> m;
    for (i = 1; i <= n; i++)
        cin >> a[i] + 1;
    ways[n][m] = 1;
    for (i = n; i; i--)
        for (j = m; j; j--)
            if (!(i == n && j == m))
                ways[i][j] = ways[i][j + 1] + ways[i + 1][j];
    i = 1, j = 1;
    ll k;
    cin >> k;
    cout << a[i][j];
    while (!(i == n && j == m))
    {
        if (i != n && j != m)
        {
            pair <int, int> minloc = {i + 1, j};
            if (a[i + 1][j] > a[i][j + 1])
                minloc = {i, j + 1};
            if (k > ways[minloc.f][minloc.s])
            {
                k -= ways[minloc.f][minloc.s];
                i = 2 * i + 1 - minloc.f;
                j = 2 * j + 1 - minloc.s;
            }
            else
            {
                i = minloc.f;
                j = minloc.s;
            }
        }
        else
        if (i == n)
            j++;
        else
            i++;
        cout << a[i][j];
    }
    return 0;
}

Compilation message

kthpath.cpp: In function 'int main()':
kthpath.cpp:17:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   17 |         cin >> a[i] + 1;
      |                ~~~~~^~~

Subtask #1
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 Incorrect 1 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -