Submission #20590743

---

Source Code Expand

#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 int
#define cel(x,y)				(x+y-1)/y
#define flr(x,y)				x/y
#define endl					"\n"
#define pb 						push_back
#define pii 					pair<int,int>
#define psi 					pair<string,int>
#define vi 						vector<int>
#define pqi 					priority_queue<int>
#define pqim 					priority_queue<int,vector<int>,greater<int>>
#define umis 					unordered_map<int,string>
#define umii 					unordered_map<int,int>
#define msi 				    map<string,int>
#define mii 				    map<int,int>
#define setbits(n)			    __builtin_popcountll(n) // for long long
#define zrbits(n)			    __builtin_ctzll(n)
#define f(i,x,n)			    for(int i=x;i<n;++i)
#define mod			    		1000000007
#define sp(x,y)			    	fixed<<setprecision(y)<<x
mt19937							rng(chrono::steady_clock::now().time_since_epoch().count());
#define fastio                  ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

void setup() {
	// for fast input output
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
}

int power(int a, int  n) {
	int val;
	if (n == 0) return 1;
	else if (n % 2 == 0)
	{
		val = power(a, n / 2);
		return  val * val;
	}
	else {
		val = power(a, n / 2);
		return a * val * val;
	}
}

int GCD(int a, int b) { if (b == 0) return a; return GCD(b, a % b);}

int LCM(int a, int b) {return (a * b) / GCD(a, b);}

int min(int a, int b) {if (a > b) return b; else return a;}

int max(int a, int b) {if (a > b) return a; else return b;}

// ============================================================================================================
int32_t main() {

	//setup();
	fastio;
	string s, t;
	cin >> s >> t;

	int n = s.length(), m = t.length();
	string dp[n][m];
	bool flag = false;
	for (int i = 0; i < n; ++i) {
		if (!flag and s[i] == t[0]) {
			dp[i][0] = t[0];
			flag = true;
		}
		else if (flag) {
			dp[i][0] = t[0];
		}
	}
	flag = false;
	for (int j = 0; j < m; ++j) {
		if (!flag and t[j] == s[0]) {
			dp[0][j] = s[0];
			flag = true;
		}
		else if (flag) {
			dp[0][j] = s[0];
		}
	}
	for (int i = 1; i < n; ++i) {
		for (int j = 1; j < m; ++j) {
			if (s[i] == t[j]) {
				string x = dp[i - 1][j - 1] + s[i];
				string y = dp[i][j - 1];
				string z = dp[i - 1][j];
				if (x.length() >= y.length() and x.length() >=  z.length()) {
					dp[i][j] = x;
				}
				else if (y.length() >= x.length() and y.length() >=  z.length()) {
					dp[i][j] = y;
				}
				else {
					dp[i][j] = z;
				}
			}
			else {
				string y = dp[i][j - 1];
				string z = dp[i - 1][j];
				if (y.length() >= z.length()) {
					dp[i][j] = y;
				}
				else {
					dp[i][j] = z;
				}
			}
		}
	}
	cout << dp[n - 1][m - 1] << endl;
	return 0;
}

Submission Info

Judge Result