oj.uz

Submission #346329

# Submission time Handle Problem Language Result Execution time Memory
346329 2021-01-09T11:38:46 Z nicolaalexandra K-th path (IZhO11_kthpath) C++14
100 / 100
 4 ms 492 KB 
#include <bits/stdc++.h>
#define DIM 40
#define INF 1000000000000000000LL
using namespace std;

long long dp[DIM][DIM],cnt[DIM][DIM];
char sol[DIM*2],s[DIM][DIM];
long long k;
int n,m,i,j;

int solve (int val, char ch){

    memset (dp,0,sizeof dp);

    long long total = 0;
    int i,j;

    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++){
            if (i == 1 && j == 1){
                dp[i][j] = 1;
                continue;
            }

            int dist = i + j - 1;
            if (dist > val)
                continue;

            long long nr = min(INF,dp[i][j-1] + dp[i-1][j]);

            if (s[i][j] < sol[dist] || (dist == val && s[i][j] == sol[dist])){
                if (nr > INF / cnt[i][j])
                    total = INF;
                total = min (INF, total + nr * cnt[i][j]);
                //total += nr * cnt[i][j];
            }


            if (s[i][j] == sol[dist])
                dp[i][j] = nr;

        }

    if (total < k)
        return 0;

    return 1;
}

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n>>m;
    for (i=1;i<=n;i++)
        cin>>s[i]+1;

    cin>>k;

    for (i=n;i;i--)
        for (j=m;j;j--){
            if (i == n && j == m){
                cnt[n][m] = 1;
                continue;
            }
            cnt[i][j] = min(INF,cnt[i][j+1] + cnt[i+1][j]);
        }


    sol[1] = s[1][1];
    for (i=2;i<=n+m-1;i++){
        for (char ch='a';ch<='z';ch++){
            sol[i] = ch;
            if (solve (i,ch))
                break;

        }
    }

    for (i=1;i<=n+m-1;i++)
        cout<<sol[i];


    return 0;
}

Compilation message

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

Subtask #1
100.0 / 100.0

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