#845816 (C++17) No.2234 palindromer

• 問題: No.2234 palindromer
• ユーザー: harshith akkapelli
• 提出日時: 2023-03-03 22:33:06
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 2 ms / 2,000 ms
• コード長: 1,141 bytes
• コンパイル時間: 2,022 ms
• コンパイル使用メモリ: 210,236 KB
• 実行使用メモリ: 6,944 KB
• 最終ジャッジ日時: 2024-09-17 23:33:31
• 合計ジャッジ時間: 2,582 ms
• ジャッジサーバーID （参考情報）: judge3 / judge6

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 6,816 KB
testcase_01	AC	1 ms; 6,940 KB
testcase_02	AC	2 ms; 6,940 KB
testcase_03	AC	1 ms; 6,944 KB
testcase_04	AC	1 ms; 6,940 KB
testcase_05	AC	1 ms; 6,944 KB
testcase_06	AC	2 ms; 6,940 KB
testcase_07	AC	1 ms; 6,940 KB
testcase_08	AC	2 ms; 6,940 KB
testcase_09	AC	1 ms; 6,944 KB
testcase_10	AC	1 ms; 6,944 KB
testcase_11	AC	1 ms; 6,944 KB
testcase_12	AC	2 ms; 6,940 KB
testcase_13	AC	1 ms; 6,940 KB
testcase_14	AC	1 ms; 6,940 KB
testcase_15	AC	1 ms; 6,940 KB

ソースコード

#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
typedef long long int ll;
using T_=pair<ll,ll>;


void routine(){
	string a;
	cin >> a;
	bool isPali = true;
	int n = a.size();
	for(ll i = 0;i < n/2;i++){
		if(a[i]!=a[n-i-1]) isPali=false;
	}
	if(isPali){
		cout << a << "\n";
		return;
	}
	vector<vector<bool>> dp(n+1,vector<bool>(n+1,false));
	for(ll i = 1;i <= n;i++) dp[i][i]=true;
	for(ll i = 1;i <=n;i++){
		ll j = i-1,k = i+1;
		while(j>=1 and k <= n and a[j-1]==a[k-1]){
			dp[j][k]=dp[j+1][k-1];
			if(dp[j][k]==false) break;
			j--;
			k++;
		}
		j = i-1,k=i;
		if(a[j-1]==a[k-1]) dp[j][k]=true;
		j--;k++;
		while(j>=1 and k <= n and a[j-1]==a[k-1]){
			dp[j][k]=dp[j+1][k-1];
			if(dp[j][k]==false) break;
			j--;
			k++;
		}		
	}
	ll ind = 0;
	for(ll i = 1;i <= n;i++){
		if(dp[i][n]){
			ind =  i;
			break;
		}
	}
	//cout << ind << "\n";
	string ans = "";
	ans += a;
	string b = a;
	a = a.substr(0,ind-1);
	reverse(begin(a),end(a));
	ans += a;
	cout << ans << "\n";
	return;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	ll t = 1;
	while(t--){
		routine();
	}
	return 0;
}