Submission #89734

#	Time	Username	Problem	Language	Result	Execution time	Memory
89734		popovicirobert	K-th path (IZhO11_kthpath)	C++14	0 / 100	2 ms	504 KiB

kthpath

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const ll INF = 1e18 + 5;
const int MAXN = 30;

char mat[MAXN + 1][MAXN + 1];
ll dp[MAXN + 1][MAXN + 1];
bool vis1[MAXN + 1][MAXN + 1], vis2[MAXN + 1][MAXN + 1];

inline void add(ll &x, ll y) {
    x += y;
    if(x > INF)
        x = INF;
}

int main() {
    ifstream cin("kthpath.in");
    ofstream cout("kthpath.out");
    int i, j, n, m;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for(i = 1; i <= n; i++) {
        cin >> mat[i] + 1;
    }
    ll k;
    cin >> k;
    dp[n][m] = 1;
    for(i = n; i >= 1; i--) {
        for(j = m; j >= 1; j--) {
            add(dp[i][j], dp[i + 1][j] + dp[i][j + 1]);
        }
    }
    /*for(i = 1; i <= n; i++) {
        for(j = 1; j <= m; j++) {
            cerr << dp[i][j] << " ";
        }
        cerr << "\n";
    }*/
    vector <char> sol;
    sol.push_back(mat[1][1] - 'a');
    vector < pair <int, int> > cur;
    cur.push_back({1, 1});
    while(cur.size()) {
        vector < pair <int, int> > aux;
        vector <ll> fr(26);
        for(auto it : cur) {
            int l = it.first, c = it.second;
            if(l + 1 <= n) {
                add(fr[mat[l + 1][c] - 'a'], dp[l + 1][c]);
            }
            if(c + 1 <= m) {
                add(fr[mat[l][c + 1] - 'a'], dp[l][c + 1]);
            }
        }
        char ch = -1;
        ll s = 0;
        for(i = 0; i < 26; i++) {
            s += fr[i];
            if(s >= k) {
                k -= (s - fr[i]);
                ch = i;
                break;
            }
        }
        if(ch != -1) {
            sol.push_back(ch);
        }
        for(auto it : cur) {
            int l = it.first, c = it.second;
            if(l < n && mat[l + 1][c] == ch + 'a') {
                aux.push_back({l + 1, c});
            }
            if(c < m && mat[l][c + 1] == ch + 'a') {
                aux.push_back({l, c + 1});
            }
        }
        cur = aux;
    }
    for(auto it : sol) {
        cout << (char) (it + 'a');
    }
    cin.close();
    cout.close();
    return 0;
}

Compilation message (stderr)

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

• Subtask 1: 0 / 100