Submission #89750

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
89750	2018-12-18T09:22:00 Z	popovicirobert	K-th path (IZhO11_kthpath)	C++14	100 / 100	2 ms	832 KB

kthpath

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

using namespace std;

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

char mat[MAXN + 1][MAXN + 1];
ll dp[MAXN + 1][MAXN + 1];

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

ll cnt[MAXN + 1][MAXN + 1], new_cnt[MAXN + 1][MAXN + 1];

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.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');
    cnt[1][1] = 1;
    while(1) {
        memset(new_cnt, 0, sizeof(new_cnt));
        vector <ll> fr(26);
        for(i = 1; i <= n; i++) {
            for(j = 1; j <= m; j++) {
                if(cnt[i][j]) {
                    if(i < n) {
                        if(INF / dp[i + 1][j] > cnt[i][j]) {
                            add(fr[mat[i + 1][j] - 'a'], 1LL * cnt[i][j] * dp[i + 1][j]);
                        }
                        else {
                            fr[mat[i + 1][j] - 'a'] = INF;
                        }
                    }
                    if(j < m) {
                        if(INF / dp[i][j + 1] > cnt[i][j]) {
                            add(fr[mat[i][j + 1] - 'a'], 1LL * cnt[i][j] * dp[i][j + 1]);
                        }
                        else {
                            fr[mat[i][j + 1] - 'a'] = INF;
                        }
                    }
                }
            }
        }
        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;
            }
        }
        //cerr << k << "\n";
        if(ch == -1) {
            break;
        }
    //cerr << k << " " << (char) (ch + 'a')  << "\n";
        sol.push_back(ch);
        for(i = 1; i <= n; i++) {
            for(j = 1; j <= m; j++) {
                if(cnt[i][j]) {
                    if(i < n && mat[i + 1][j] == ch + 'a') {
                        add(new_cnt[i + 1][j], cnt[i][j]);
                    }
                    if(j < m && mat[i][j + 1] == ch + 'a') {
                        add(new_cnt[i][j + 1], cnt[i][j]);
                    }
                }
            }
        }
        for(i = 1; i <= n; i++) {
            for(j = 1; j <= m; j++) {
                cnt[i][j] = new_cnt[i][j];
            }
        }
    }
    for(auto it : sol) {
        cout << (char) (it + 'a');
    }
    //cin.close();
    //cout.close();
    return 0;
}

Compilation message

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

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	576 KB	Output is correct
3	Correct	2 ms	624 KB	Output is correct
4	Correct	2 ms	624 KB	Output is correct
5	Correct	2 ms	740 KB	Output is correct
6	Correct	2 ms	740 KB	Output is correct
7	Correct	2 ms	740 KB	Output is correct
8	Correct	2 ms	740 KB	Output is correct
9	Correct	2 ms	796 KB	Output is correct
10	Correct	2 ms	796 KB	Output is correct
11	Correct	2 ms	796 KB	Output is correct
12	Correct	2 ms	796 KB	Output is correct
13	Correct	2 ms	796 KB	Output is correct
14	Correct	2 ms	828 KB	Output is correct
15	Correct	2 ms	832 KB	Output is correct
16	Correct	2 ms	832 KB	Output is correct
17	Correct	2 ms	832 KB	Output is correct
18	Correct	2 ms	832 KB	Output is correct
19	Correct	2 ms	832 KB	Output is correct
20	Correct	2 ms	832 KB	Output is correct