oj.uz

Submission #864352

# Submission time Handle Problem Language Result Execution time Memory
864352 2023-10-22T15:20:12 Z Ariadna Pohlepko (COCI16_pohlepko) C++14
30 / 80
 1000 ms 65536 KB 
#include <bits/stdc++.h>

using namespace std;

int n, m;
vector < vector < char > > grid;
vector < vector < int > > adj;
string s = "", ans = "";

void dfs(int u) {
    int i = u / m, j = u % m;
    s += grid[i][j];
    if (u == n * m - 1) {
        if (ans == "") ans = s;
        else ans = min(ans, s);
    } else {
        if (i == n - 1) dfs(u + 1);
        else if (j == m - 1) dfs(u + 1);
        else {
            if (grid[i + 1][j] <= grid[i][j + 1]) dfs(u + m);
            if (grid[i + 1][j] >= grid[i][j + 1]) dfs(u + 1);
        }
        
    }
    s.pop_back();
}

int main()
{
    cin >> n >> m;
    grid = vector < vector < char > >(n, vector < char >(m));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> grid[i][j];
        }
    }
    adj = vector < vector < int > >(n * m);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (i < n - 1) adj[i * m + j].push_back((i + 1) * m + j);
            if (j < m - 1) adj[i * m + j].push_back(i * m + j + 1);
        }
    }
    dfs(0);
    cout << ans << '\n';
    
    return 0;
}

Subtask #1
30.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 27 ms 13916 KB Output is correct
7 Runtime error 112 ms 65536 KB Execution killed with signal 9
8 Runtime error 138 ms 65536 KB Execution killed with signal 9
9 Incorrect 5 ms 600 KB Output isn't correct
10 Execution timed out 1078 ms 3676 KB Time limit exceeded
11 Execution timed out 1032 ms 7076 KB Time limit exceeded
12 Execution timed out 1034 ms 19020 KB Time limit exceeded
13 Execution timed out 1049 ms 11600 KB Time limit exceeded
14 Runtime error 142 ms 65536 KB Execution killed with signal 9
15 Execution timed out 1044 ms 1300 KB Time limit exceeded
16 Runtime error 110 ms 65536 KB Execution killed with signal 9