oj.uz

Submission #89741

# Submission time Handle Problem Language Result Execution time Memory
89741 2018-12-18T09:02:28 Z popovicirobert K-th path (IZhO11_kthpath) C++14
0 / 100
 1033 ms 263168 KB 
#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;
}

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');
    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

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

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 576 KB Output is correct
4 Correct 2 ms 576 KB Output is correct
5 Correct 2 ms 600 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 2 ms 608 KB Output is correct
8 Correct 2 ms 652 KB Output is correct
9 Correct 2 ms 660 KB Output is correct
10 Runtime error 1033 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Halted 0 ms 0 KB -