Submission #864360

#	Time	Username	Problem	Language	Result	Execution time	Memory
864360		Ariadna	Pohlepko (COCI16_pohlepko)	C++14	65 / 80	158 ms	65536 KiB

pohlepko

#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 / 80