oj.uz

Submission #346328

# Submission time Handle Problem Language Result Execution time Memory
346328 2021-01-09T11:37:54 Z nicolaalexandra K-th path (IZhO11_kthpath) C++14
0 / 100
 2 ms 384 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;

            int 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
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 384 KB Output is correct
8 Correct 1 ms 376 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Incorrect 2 ms 364 KB Output isn't correct
11 Halted 0 ms 0 KB -