fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/numeric>
  3. //#include <ext/hash_map>
  4. using namespace std;
  5. using namespace __gnu_cxx;
  6.  
  7. #define oo			1e9
  8. #define OO			1e18
  9. #define EPS			1e-7
  10. #define f			first
  11. #define s			second
  12. #define ll			long long
  13. #define pi 			acos(-1.0)
  14. #define sz(x)		(int)x.size()
  15. #define all(x)		x.begin(),x.end()
  16. #define rall(x)		x.rbegin(),x.rend()
  17. #define popCnt(x)   __builtin_popcount(x)
  18.  
  19. int dp[55][55];
  20. string str;
  21.  
  22. int getCost(int i,int j){
  23. 	if(str[i]=='('&&str[j]=='(')return 1;
  24. 	if(str[i]=='('&&str[j]==')')return 0;
  25. 	if(str[i]==')'&&str[j]=='(')return 2;
  26. 	if(str[i]==')'&&str[j]==')')return 1;
  27. 	return 0;
  28. }
  29.  
  30. int solve(int i,int j){
  31. 	if(j<=i)return (i==j?oo:0);
  32. 	int &ret=dp[i][j];
  33. 	if(~ret)return ret;
  34. 	ret=solve(i+1,j-1)+getCost(i,j);
  35. 	for(int k=i;k<=j;k++)
  36. 		ret=min(ret,solve(i,k)+solve(k+1,j));
  37. 	return ret;
  38. }
  39.  
  40. vector<int> ans;
  41.  
  42. void getAns(int i,int j){
  43. 	if(j<=i)return;
  44. 	int ch=solve(i+1,j-1)+getCost(i,j);
  45. 	for(int k=i;k<=j;k++)
  46. 		ch=min(ch,solve(i,k)+solve(k+1,j));
  47. 	if(solve(i+1,j-1)+getCost(i,j)==ch){
  48. 		if(str[i]!='(')ans.push_back(i);
  49. 		if(str[j]!=')')ans.push_back(j);
  50. 		getAns(i+1,j-1);
  51. 	}
  52. 	else
  53. 	for(int k=i;k<=j;k++){
  54. 		if(solve(i,k)+solve(k+1,j)==ch){
  55. 			getAns(i,k);
  56. 			getAns(k+1,j);
  57. 			break;
  58. 		}
  59. 	}
  60. }
  61.  
  62.  
  63. class ParenthesesDiv2Medium{
  64. public:
  65. 	vector <int> correct(string s){
  66. 		str=s;
  67. 		memset(dp,-1,sizeof dp);
  68. 		solve(0,sz(s)-1);
  69. 		getAns(0,sz(s)-1);
  70. 		sort(all(ans));
  71. 		return ans;
  72. 	}
  73. };
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
/usr/lib/gcc/i586-linux-gnu/5/../../../i386-linux-gnu/crt1.o: In function `_start':
(.text+0x18): undefined reference to `main'
collect2: error: ld returned 1 exit status
stdout
copy 
Standard output is empty
https://ideone.com/Fk6i1j
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!