Submission #104293

#	Time	Username	Problem	Language	Result	Execution time	Memory
104293		leonarda	Pohlepko (COCI16_pohlepko)	C++14	15 / 80	1077 ms	39672 KiB

pohlepko

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
typedef pair<int, int> pi;
typedef long long int lint;
const int inf = 0x3f3f3f3f;
const int maxn = 2000 + 5;

int n, m;
char a[maxn][maxn];
char dp[maxn][maxn];
pair<int, int> src[maxn][maxn];
string rjesenje;

pair<char, char> fuki(int x1, int y1, int x2, int y2) {
	while(a[x1][y1] == a[x2][y2]) {
		tie(x1, y1) = src[x1][y1];
		tie(x2, y2) = src[x2][y2];
		if(x1 == -1 or x2 == -1) return mp(0, 0);
	}
	return mp(a[x1][y1], a[x2][y2]);
}

int main ()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> n >> m;
	for(int i = 0; i < n; ++i)
		for(int j = 0; j < m; ++j)
			cin >> a[i][j];
	
	dp[0][0] = a[0][0];
	src[0][0] = mp(-1, -1);
	
	for(int i = 1; i < m; ++i) {
		dp[0][i] = dp[0][i - 1];
		src[0][i] = mp(0, i - 1);
	}
	
	for(int i = 1; i < n; ++i) {
		dp[i][0] = dp[i - 1][0];
		src[i][0] = mp(i - 1, 0);
	}
	
	for(int i = 1; i < n; ++i) {
		for(int j = 1; j < m; ++j) {
			if(dp[i][j - 1] < dp[i - 1][j]) {
				dp[i][j] = dp[i][j - 1];
				src[i][j] = mp(i, j - 1);
			} else if(dp[i - 1][j] < dp[i][j - 1]) {
				dp[i][j] = dp[i - 1][j];
				src[i][j] = mp(i - 1, j);
			} else {
				char t1, t2;
				tie(t1, t2) = fuki(i - 1, j, i, j - 1);
				if(t1 == t2) {
					dp[i][j] = dp[i - 1][j];
					src[i][j] = mp(i - 1, j);
				} else if(t1 < t2){
					dp[i][j] = t1;
					src[i][j] = mp(i - 1, j);
				} else {
					dp[i][j] = t2;
					src[i][j] = mp(i, j - 1);
				}		
			}
		}
	}
	
	int curx = n - 1, cury = m - 1;
	while(curx != -1) {
		rjesenje.pb(a[curx][cury]);
		tie(curx, cury) = src[curx][cury];
	}
	
	for(int i = rjesenje.size() - 1; i >= 0; --i)
		cout << rjesenje[i];

return 0;
}
//written and directed by pcelica maja

• Subtask 1: 15 / 80