Submission #499020

#	Time	Username	Problem	Language	Result	Execution time	Memory
499020		PoPularPlusPlus	Pohlepko (COCI16_pohlepko)	C++17	80 / 80	244 ms	11980 KiB

pohlepko

#include <bits/stdc++.h>
using namespace std;

int main() {
	// your code goes here
	int n , m;
	cin >> n >> m;
	char arr[n][m];
	for(int i = 0; i < n; i++){
	    for(int j = 0; j < m; j++)cin >> arr[i][j];
	}
	bool vis[n][m];
	memset(vis,0,sizeof vis);
	vis[0][0] = 1;
	if(n > 1)vis[1][0] = 1;
    if(m > 1)vis[0][1] = 1;
	for(int di = 1; di < n + m; di++){
	    char mn = 'z';
	    for(int j = 0; j <= min(di , m - 1); j++){
	        if(di - j >= n){
	            continue;
	        }
	        int i = di - j;
	        if(vis[i][j]){
	            mn = min(mn , arr[i][j]);
	        }
	    }
	    for(int j = 0; j <= min(di , m - 1); j++){
	        if(di - j >= n){
	            continue;
	        }
	        int i = di - j;
	        if(vis[i][j]){
	            if(mn == arr[i][j]){
	                if(i + 1 < n)vis[i + 1][j] = 1;
	                if(j + 1 < m)vis[i][j + 1] = 1;
	            }
	            else vis[i][j] = 0;
	        }
	    }
	}
	string ans = "";
	ans += arr[n-1][m-1];
	int i = n-1 , j = m - 1;
	while(i != 0 || j != 0){
	    if(i - 1 >= 0 && vis[i-1][j]){
	       i--;
	       ans += arr[i][j];
	    }
	    else {
	        j--;
	        ans += arr[i][j];
	    }
	}
	reverse(ans.begin() , ans.end());
	cout << ans << '\n';
	return 0;
}

• Subtask 1: 80 / 80