QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#591585	#5534. Match	ifffer_2137	37	1585ms	153220kb	C++14	1.1kb	2024-09-26 16:38:22	2024-09-26 16:38:23

Judging History

你现在查看的是最新测评结果

[2024-09-26 16:38:23]
评测

测评结果：37
用时：1585ms
内存：153220kb

查看

[2024-09-26 16:38:22]
提交

answer

//From: ifffer_2137
#include <bits/stdc++.h>
using namespace std;
#define inf 0x7fffffff
#define eb emplace_back
#define pii pair<int,int>
#define mkpr make_pair
#define fir first
#define sec second
inline int read(){
	char ch=getchar();int x=0,w=1;
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+ch-48,ch=getchar();return w==1?x:-x;
}
const int maxn=2e3+5;
int n;
string s;
string dp[maxn][maxn];
signed main(){
	#ifndef ONLINE_JUDGE
	freopen("data.in","r",stdin);
	freopen("test.out","w",stdout);
	#endif
	cin.tie(0),cout.tie(0);
	cin>>s;n=s.size();s=' '+s;
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) dp[i][j]="0";
	for(int i=2;i<=n;i++){
		for(int l=1;l+i-1<=n;l++){
			int r=i+l-1;
			if(s[l]==s[r]){
				if(l+1<r&&dp[l+1][r-1]!="0") dp[l][r]=min(dp[l][r],'('+dp[l+1][r-1]+')');
				else if(l+1==r) dp[l][r]=min(dp[l][r],(string){"()"});
			}
			for(int j=l;j<r;j++){
				if(dp[l][j]=="0"||dp[j+1][r]=="0") continue;
				dp[l][r]=min(dp[l][r],dp[l][j]+dp[j+1][r]);
			}
		}
	}
	if(dp[1][n]=="0") puts("-1");
	else cout<<dp[1][n]<<"\n";
	return 0;
}

源文件, 语言: C++14

詳細信息

Subtask #1:

score: 10

Accepted

Test #1:

score: 10

Accepted

time: 11ms

memory: 129248kb

input:

abbaaa

output:

(()())

result:

ok single line: '(()())'

Test #2:

score: 10

Accepted

time: 19ms

memory: 129140kb

input:

cbbbbccbbccbbbbbbc

output:

(((((((()))())))))

result:

ok single line: '(((((((()))())))))'

Test #3:

score: 10

Accepted

time: 11ms

memory: 129184kb

input:

ddbcbdacccbddaba

output:

-1

result:

ok single line: '-1'

Subtask #2:

score: 27

Accepted

Dependency #1:

100%

Accepted

Test #4:

score: 27

Accepted

time: 199ms

memory: 129532kb

input:

fsooskkkksokkkkossskkiffoofooikkiiiiiooikkkksookkiissiooookskffsskiiksskiikfiifkifofssooffffkfiiiifkfsiisfsofossiffissikskiikkkiikokikkffkiiksffkkiossifkiookioffoikkkoiiiooioiffkkkssfoooiiiioioskksisikkkoifiooikkkkfiffississkskiofffiffiiiosksskfffofisksksskiisikkskkkksoosiffoofoiooioooifiifssfffffoi...

output:

((((((())))(()))(((()(((()((((()(()))))((((((()((((())(())((((((((())))(()))()))((((((()((()(((()))))(())))((((((())))(((((((()())(((((())())(()()((()(((((((((()))()))(()())))()())())(()(()))))(()))))()))(((())(())))())())())))))())(()())))(())()))))))((())())))))))))(()))))())((())()))(())))((())((...

result:

ok single line: '((((((())))(()))(((()(((()((((...))(())(()))(())())))))))((())))'

Test #5:

score: 27

Accepted

time: 214ms

memory: 129272kb

input:

vvrookjqmmooqlfhnnhflrcbxuuxftajjcqdppoowsswniwsswzzvvisqqbxqniinqeeeaanojvhhttviezzxujjuxyyektlltkoouwwukcqqcifommxxorrnnfgzzyggygvzzvgtxqqxkkummpssllpubbssuubddbebttkkblzzofmmyooyfoqqlpnzznppmvbnnlrrqqlwwbeiievxcnnwppweasjhcchjcarobbogljjlqqgznffmlfabjpiipepummubbbbggzzpjjvvejvgmmqrrkffkqgefrrdbbd...

output:

()(()(((()())(((())))((((())(((()(((((()(())(((())()())(()((((()))(()()((((()(((((()((()))())((())(()(()))(())(((()())()())(()(())((()))((())()(()(()())(()()))(())((()())(()((()(())))())((())()(((()(()())())(()))((()(())(((((()))((((())((())()(((()(((((((())(((())(())()())()()))((()(()(())))((()(())...

result:

ok single line: '()(()(((()())(((())))((((())((...()(()(()))))(())()))(()()()))))'

Test #6:

score: 27

Accepted

time: 925ms

memory: 153220kb

input:

uuueeeuuueeueeeeeeeuueueueeuuuuueeeueeeeeueueueuueuueeueuuuuuuueueueeuueeueeuueeueuueeeueuueeeueueueuueuuueeeeueuuuuueuueueueuuueuuueeeeuueeueeeeeuuuueeeeeuuuueeuuuueueeueuueuuueeeeuueueueueeeeeeeuueueuuueuuuueueeuuueuuuueuuueeuueeeeueeuueuuuuuuuuueeeueuuueueeueeeeuueeuuuueuueeuuueuueeuuueeueeuueueu...

output:

((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...

result:

ok single line: '((((((((((((((((((((((((((((((...)))))))))))))))))))))))))))))))'

Test #7:

score: 27

Accepted

time: 1585ms

memory: 131592kb

input:

qeeqqqeeqqqquqeeeequuquuuqqqeqqqeeqquqqeeeuuueqqeeqqqqqeeeeeeeeeuqeqquuueeuqeqeqqueeuuuueeeeuuuqqquueuqeeeqeeeqeeqeqqequeeueqquuquqququqqqqueuqueuuuueuueeuueueeququeeeqeeqeeqqeuqeuequququuuuuueuuueeeuueeeqeuqquueuueeuquuqqqeqeuqqeqqquuueuuuuueeuuqeeeeeeeueuuuququeqqqqeeuqeuuquuueueeuuuqeqeeuqqqquuuq...

output:

((((((()()))((((()(((((()(()((((()))((((()((((((()(()))((((())))((((((()()))(((((((((())()))())(()()(((((((((((((((()))(()((((())(()))((()))))((((((((((())))(()((((((((())))())(((((((((((((())((()(((()(((((((((((((())(()(((((((()(((((((((((((()()(((((((((((()((((((((((((((()((((((()())(((()((())(()(...

result:

ok single line: '((((((()()))((((()(((((()(()((...))))((())))())))((())))))()))))'

Subtask #3:

score: 0

Runtime Error

Dependency #1:

100%

Accepted

Dependency #2:

100%

Accepted

Test #8:

score: 0

Runtime Error

input:

jggeedfjvfppgdgqqufesgeljdjjoqqsgprqdddgueugpodpfldvgdgdpeuljfqrdrlgljugdujjdjrjevlqlqufoosjvsqvqgvruqrgsfsquqoovvvvfpofjdpvuesrqdfegguggrlvslsqjpddorjlodqflspgopeuppeoleeojlvjpddopjsouregflrfgpgqvlquqpplgrudllvdfsrplfljupveleggedljopqjjolslfpeeluvsufofpdlodgdvfvsujlgjpvggduorfforllorgsgrppvegglgver...