Submission #346329

#	Time	Username	Problem	Language	Result	Execution time	Memory
346329		nicolaalexandra	K-th path (IZhO11_kthpath)	C++14	100 / 100	4 ms	492 KiB

kthpath

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

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

• Subtask 1: 100 / 100