oj.uz

Submission #445632

# Submission time Handle Problem Language Result Execution time Memory
445632 2021-07-19T07:14:19 Z soroush Match (CEOI16_match) C++17
10 / 100
 2000 ms 16132 KB 
#pragma GCC target("popcnt")
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int , int> pii;
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const int maxn = 2010;
const ll mod = 1e9+7;
 
#define pb push_back
#define endl '\n'
#define dokme(x) cout << x , exit(0)
#define ms(x , y) memset(x , y , sizeof x)
ll pw(ll a, ll b, ll md = mod){ll res = 1;while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res);}
 
int n;
string s;
char ans[maxn];
int dp[maxn][maxn];
 
bool chk(int l , int r){
	if(~dp[l][r])return dp[l][r];
	if(l >= r)return (dp[l][r] = 1);
	for(int i = l + 1 ; i < r ; i ++)if(s[i] == s[l])
		if(chk(l+1, i) && chk(i+1 , r))return (dp[l][r] = 1);
	return (dp[l][r] = 0);
}
 
void solve(int l , int r){
	if(l >= r)return;
	for(int i = r - 1 ; i > l ; i --)if(s[i] == s[l])
		if(chk(l+1, i) && chk(i+1 , r)){
			ans[l] = '(' , ans[i] = ')';
			solve(l + 1 , i) , solve(i + 1 , r);
			return;
		}
}
 
int32_t main(){
	cin.tie(0)->sync_with_stdio(0);
	ms(dp , -1);
	cin >> s;
	n = s.size();
	if(chk(0 , n)){
		solve(0, n);
		for(int i = 0 ; i < n ; i ++)
			cout << ans[i];
	}
	else
		cout << -1;
	return(0);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16076 KB Output is correct
2 Correct 8 ms 16116 KB Output is correct
3 Correct 7 ms 16088 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16076 KB Output is correct
2 Correct 8 ms 16116 KB Output is correct
3 Correct 7 ms 16088 KB Output is correct
4 Correct 157 ms 16132 KB Output is correct
5 Correct 11 ms 16076 KB Output is correct
6 Correct 1285 ms 16116 KB Output is correct
7 Execution timed out 2076 ms 16076 KB Time limit exceeded

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16076 KB Output is correct
2 Correct 8 ms 16116 KB Output is correct
3 Correct 7 ms 16088 KB Output is correct
4 Correct 157 ms 16132 KB Output is correct
5 Correct 11 ms 16076 KB Output is correct
6 Correct 1285 ms 16116 KB Output is correct
7 Execution timed out 2076 ms 16076 KB Time limit exceeded