oj.uz

Submission #864360

# Submission time Handle Problem Language Result Execution time Memory
864360 2023-10-22T15:33:51 Z Ariadna Pohlepko (COCI16_pohlepko) C++14
65 / 80
 158 ms 65536 KB 
#include <bits/stdc++.h>

using namespace std;

int n, m;
vector < vector < char > > grid;
vector < vector < string > > dp;

string dfs(int i, int j) {
    if (dp[i][j] != ".") return dp[i][j];
    dp[i][j] = grid[i][j];
    if (i < n - 1 || j < m - 1) {
        if (i == n - 1) dp[i][j] += dfs(i, j + 1);
        else if (j == m - 1) dp[i][j] += dfs(i + 1, j);
        else {
            if (grid[i + 1][j] == grid[i][j + 1]) dp[i][j] += min(dfs(i + 1, j), dfs(i, j + 1));
            else if (grid[i + 1][j] < grid[i][j + 1]) dp[i][j] += dfs(i + 1, j);
            else dp[i][j] += dfs(i, j + 1);
        }
        
    }
    return dp[i][j];
}

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];
        }
    }
    
    dp = vector < vector < string > >(n, vector < string >(m, "."));
    cout << dfs(0, 0) << '\n';
    
    return 0;
}

Subtask #1
65.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 500 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 11 ms 8792 KB Output is correct
7 Correct 63 ms 46848 KB Output is correct
8 Runtime error 154 ms 65536 KB Execution killed with signal 9
9 Correct 1 ms 604 KB Output is correct
10 Correct 4 ms 2908 KB Output is correct
11 Correct 7 ms 5680 KB Output is correct
12 Correct 17 ms 14172 KB Output is correct
13 Correct 11 ms 9976 KB Output is correct
14 Runtime error 158 ms 65536 KB Execution killed with signal 9
15 Correct 4 ms 2904 KB Output is correct
16 Runtime error 82 ms 65536 KB Execution killed with signal 9