oj.uz

답안 #864360

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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