Submission #3995873
Source Code Expand
#include<cstdio> #include<cstring> #include<algorithm> #define INF 500 using namespace std; int n,dp[101][101][101],ans=INF; int main(){ char s[110]; scanf("%s",s); n=strlen(s); for(int i=0;i<=n;i++){ for(int j=0;j<=n;j++){ for(int k=0;k<=n;k++){ dp[i][j][k]=INF; } } } dp[0][0][0]=0; for(int i=0;i<=n;i++){ for(int j=0;j<=i;j++){ //printf("%d %d\n",i,j); for(int k=0;k<=i;k++){ if(j>i||k>i); else{ if(i==0) continue; if(s[i-1]=='('){ if(j!=0&&k<i){ dp[i][j][k]=dp[i-1][j-1][k]; } if(j!=n){ dp[i][j][i]=min(dp[i][j][i],dp[i-1][j+1][k]+1); } } else{ if(j!=n&&k<i){ dp[i][j][k]=dp[i-1][j+1][k]; } if(j!=0){ dp[i][j][i]=min(dp[i][j][i],dp[i-1][j-1][k]+1); } } } //printf("%d ",dp[i][j][k]); } //printf("\n"); } } ans=dp[n][0][0]; for(int i=1;i<=n;i++){ ans=min(ans,i+dp[n][0][i]-1); } printf("%d\n",ans); }
Submission Info
Submission Time | |
---|---|
Task | B - 天下一魔力発電 |
User | AC961009 |
Language | C++14 (GCC 5.4.1) |
Score | 400 |
Code Size | 1505 Byte |
Status | AC |
Exec Time | 4 ms |
Memory | 4224 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:10:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%s",s); ^
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 | 1 ms | 256 KB |
01_sample_02 | AC | 1 ms | 256 KB |
01_sample_03 | AC | 1 ms | 256 KB |
02_manual_01 | AC | 1 ms | 128 KB |
02_manual_02 | AC | 1 ms | 256 KB |
02_manual_03 | AC | 1 ms | 256 KB |
10_random_00 | AC | 1 ms | 1024 KB |
10_random_01 | AC | 1 ms | 256 KB |
10_random_02 | AC | 1 ms | 896 KB |
10_random_03 | AC | 2 ms | 2432 KB |
10_random_04 | AC | 1 ms | 256 KB |
10_random_05 | AC | 1 ms | 512 KB |
10_random_06 | AC | 1 ms | 1024 KB |
10_random_07 | AC | 3 ms | 3968 KB |
10_random_08 | AC | 2 ms | 1920 KB |
10_random_09 | AC | 1 ms | 512 KB |
10_random_10 | AC | 1 ms | 384 KB |
10_random_11 | AC | 1 ms | 256 KB |
10_random_12 | AC | 3 ms | 3200 KB |
10_random_13 | AC | 3 ms | 3328 KB |
10_random_14 | AC | 1 ms | 384 KB |
10_random_15 | AC | 1 ms | 512 KB |
10_random_16 | AC | 3 ms | 3840 KB |
10_random_17 | AC | 3 ms | 3584 KB |
10_random_18 | AC | 3 ms | 3840 KB |
10_random_19 | AC | 3 ms | 3840 KB |
20_max_00 | AC | 4 ms | 4224 KB |
20_max_01 | AC | 4 ms | 4224 KB |
20_max_02 | AC | 4 ms | 4224 KB |
20_max_03 | AC | 4 ms | 4224 KB |
20_max_04 | AC | 4 ms | 4224 KB |
20_max_05 | AC | 4 ms | 4224 KB |