Submission #498832

#	Time	Username	Problem	Language	Result	Execution time	Memory
498832		Sad_Bus	Pohlepko (COCI16_pohlepko)	C++14	0 / 80	41 ms	65540 KiB

pohlepko

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define int long long
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
#define intmin -100000000000000000LL
#define intmax 100000000000000000LL

vector<vector<int>> arr(2002, vector<int>(2002, -1));
vector<vector<string>> dp(2002, vector<string>(2002, "!"));

int n, m;
string recurse(int i, int j){
	if(i > n || j > m){
		return "~";
	}
	if(dp[i][j] != "!"){
		return dp[i][j];
	}
	string ans = "";
	ans += char(97+arr[i][j]);
	if(i == n && j == m){
		return dp[i][j] = ans;
	}

	ans += min(recurse(i+1, j), recurse(i, j+1));
	return dp[i][j] = ans;
}

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n >> m;

	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			char c;
			cin >> c;
			arr[i][j] = c - 'a';
		}
	}

	cout << recurse(1, 1) << '\n';
}

• Subtask 1: 0 / 80