Submission #2105161
Source Code Expand
#include <bits/stdc++.h> using namespace std; using ll = long long; using ull = unsigned long long; #define MOD 1000000007 #define INF INT_MAX/2; int dp[110][110][110]; int main(){ string s; cin>>s; for(int i=0;i<110;i++){ for(int j=0;j<110;j++){ for(int k=0;k<110;k++){ dp[i][j][k]=INF; } } } dp[0][0][0]=0; int n=s.length(); for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ for(int k=0;k<n;k++){ if(s[i]=='('){ dp[i+1][j][k+1]=min(dp[i+1][j][k+1],dp[i][j][k]); if(k>0) dp[i+1][i][k-1]=min(dp[i+1][i][k-1],dp[i][j][k]+1); }else{ if(k>0) dp[i+1][j][k-1]=min(dp[i+1][j][k-1],dp[i][j][k]); dp[i+1][i][k+1]=min(dp[i+1][i][k+1],dp[i][j][k]+1); } } } } int ans=INF; for(int i=0;i<n;i++) ans=min(ans,dp[n][i][0]+i); cout<<ans<<endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | B - 天下一魔力発電 |
User | misosoup |
Language | C++14 (GCC 5.4.1) |
Score | 400 |
Code Size | 913 Byte |
Status | AC |
Exec Time | 7 ms |
Memory | 5504 KB |
Judge Result
Set Name | All | ||
---|---|---|---|
Score / Max Score | 400 / 400 | ||
Status |
|
Set Name | Test Cases |
---|---|
All | 01_sample_01, 01_sample_02, 01_sample_03, 02_manual_01, 02_manual_02, 02_manual_03, 10_random_00, 10_random_01, 10_random_02, 10_random_03, 10_random_04, 10_random_05, 10_random_06, 10_random_07, 10_random_08, 10_random_09, 10_random_10, 10_random_11, 10_random_12, 10_random_13, 10_random_14, 10_random_15, 10_random_16, 10_random_17, 10_random_18, 10_random_19, 20_max_00, 20_max_01, 20_max_02, 20_max_03, 20_max_04, 20_max_05 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
01_sample_01 | AC | 4 ms | 5504 KB |
01_sample_02 | AC | 4 ms | 5376 KB |
01_sample_03 | AC | 4 ms | 5504 KB |
02_manual_01 | AC | 4 ms | 5376 KB |
02_manual_02 | AC | 4 ms | 5504 KB |
02_manual_03 | AC | 4 ms | 5504 KB |
10_random_00 | AC | 4 ms | 5504 KB |
10_random_01 | AC | 4 ms | 5376 KB |
10_random_02 | AC | 4 ms | 5376 KB |
10_random_03 | AC | 5 ms | 5376 KB |
10_random_04 | AC | 4 ms | 5504 KB |
10_random_05 | AC | 4 ms | 5376 KB |
10_random_06 | AC | 4 ms | 5504 KB |
10_random_07 | AC | 6 ms | 5504 KB |
10_random_08 | AC | 4 ms | 5504 KB |
10_random_09 | AC | 4 ms | 5376 KB |
10_random_10 | AC | 4 ms | 5376 KB |
10_random_11 | AC | 4 ms | 5504 KB |
10_random_12 | AC | 5 ms | 5376 KB |
10_random_13 | AC | 5 ms | 5376 KB |
10_random_14 | AC | 4 ms | 5376 KB |
10_random_15 | AC | 4 ms | 5376 KB |
10_random_16 | AC | 6 ms | 5376 KB |
10_random_17 | AC | 6 ms | 5504 KB |
10_random_18 | AC | 6 ms | 5376 KB |
10_random_19 | AC | 6 ms | 5504 KB |
20_max_00 | AC | 7 ms | 5504 KB |
20_max_01 | AC | 6 ms | 5504 KB |
20_max_02 | AC | 6 ms | 5504 KB |
20_max_03 | AC | 6 ms | 5504 KB |
20_max_04 | AC | 6 ms | 5504 KB |
20_max_05 | AC | 6 ms | 5376 KB |