Submission #569350


Source Code Expand

#include<bits/stdc++.h>
using namespace std;

int dp[111][111];
int N,K;
string S;
int solve(int l,int r){
  if( dp[l][r] != -1 ) return dp[l][r];
  if( l == K || r == N ) return dp[l][r] = 0;
  int ret = 0;
  if( S[l] == S[r] )
    ret = max( ret, solve(l+1,r+1)+1 );
  ret = max( ret, solve(l+1,r) );
  ret = max( ret, solve(l,r+1) );
  return dp[l][r] = ret;
}

int main(){ 
  cin >>N >> S;
  int res = N;
  for(int i=0;i<N;i++){
    K = i;
    memset(dp,-1,sizeof(dp));
    // cout << K << " "<< solve(0,i)  << endl;
    res = min( res, N -solve(0,i)*2 );
  }
  cout << res << endl;
}

Submission Info

Submission Time
Task B - ヘイホー君と削除
User sate3saku3
Language C++ (GCC 4.9.2)
Score 100
Code Size 617 Byte
Status AC
Exec Time 47 ms
Memory 1152 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 4
AC × 88
Set Name Test Cases
Sample test_abacbabc.txt, test_abababab.txt, test_abcde.txt, test_26_codefestiv.txt
All test_100_bbaaababba.txt, test_100_bcbcbbccbc.txt, test_100_cccdcddccd.txt, test_100_dddccddccd.txt, test_100_kkkkjkkjkj.txt, test_100_lllklkkllk.txt, test_100_nooooonnnn.txt, test_100_prpttrstrs.txt, test_100_psupruuutq.txt, test_100_qpuutstspt.txt, test_100_qstsustsus.txt, test_100_qtrqqsqqup.txt, test_100_tpqqqrrrsp.txt, test_100_tsrrtqrqtt.txt, test_100_tussuutruq.txt, test_100_ussuttrtrs.txt, test_100_uuquqtspuu.txt, test_100_uuvvvuvvuv.txt, test_100_xxxyxxyyxx.txt, test_100_zzzyyyzyyz.txt, test_15_gunspifpdv.txt, test_17_hijkabcdab.txt, test_18_ahbicjdkea.txt, test_26_codefestiv.txt, test_33_vtootzhcdu.txt, test_72_nuauvasdgr.txt, test_73_ftnuvdtcny.txt, test_77_ksjradlaka.txt, test_77_txusqssdai.txt, test_83_amgctyikmg.txt, test_90_hseaevdcjj.txt, test_93_vpywbvvvne.txt, test_94_xliaqazebk.txt, test_98_bgefabfcgb.txt, test_98_cddabegacb.txt, test_98_cgbfcbgeed.txt, test_98_dagbdgcfbc.txt, test_98_dbcacbabad.txt, test_98_dffdbaabgf.txt, test_98_fdacgccfcd.txt, test_98_gagddgcegc.txt, test_98_gbfceggdea.txt, test_98_gddcfebeed.txt, test_a-b49.txt, test_a-b49a.txt, test_a-b50.txt, test_a-c32.txt, test_a-c32ab.txt, test_a-c33.txt, test_a-c33a.txt, test_a-pr-za-qs-z.txt, test_a-w3yyzzyyzza-w.txt, test_a-x2z46.txt, test_a-x2z47.txt, test_a-x2z52.txt, test_a-xz46a-z.txt, test_a-xz47a-z.txt, test_a-xz52a-z.txt, test_a-yy-aa-yy-a.txt, test_a-yy.txt, test_a-z.txt, test_a-z3a-u.txt, test_a-z3a-v.txt, test_a-za-z.txt, test_a-zb-za.txt, test_a-zz-a.txt, test_a3-z3.txt, test_a4-y4.txt, test_a99.txt, test_aa-y.txt, test_abababab.txt, test_abacbabc.txt, test_abcde.txt, test_az.txt, test_b100.txt, test_b4-y4dkqc.txt, test_b4-y4hhpp.txt, test_b4-z4.txt, test_byr.txt, test_kxwzajmx.txt, test_pp.txt, test_ssb4-y4ss.txt, test_x33y33z33.txt, test_x33y33z34.txt, test_x33y34z33.txt, test_x34y33z33.txt, test_z.txt, test_z98.txt
Case Name Status Exec Time Memory
test_100_bbaaababba.txt AC 36 ms 1016 KB
test_100_bcbcbbccbc.txt AC 34 ms 960 KB
test_100_cccdcddccd.txt AC 36 ms 960 KB
test_100_dddccddccd.txt AC 35 ms 1148 KB
test_100_kkkkjkkjkj.txt AC 35 ms 1052 KB
test_100_lllklkkllk.txt AC 33 ms 964 KB
test_100_nooooonnnn.txt AC 33 ms 976 KB
test_100_prpttrstrs.txt AC 35 ms 980 KB
test_100_psupruuutq.txt AC 33 ms 1056 KB
test_100_qpuutstspt.txt AC 33 ms 1020 KB
test_100_qstsustsus.txt AC 35 ms 972 KB
test_100_qtrqqsqqup.txt AC 32 ms 960 KB
test_100_tpqqqrrrsp.txt AC 35 ms 972 KB
test_100_tsrrtqrqtt.txt AC 33 ms 1020 KB
test_100_tussuutruq.txt AC 34 ms 1052 KB
test_100_ussuttrtrs.txt AC 34 ms 956 KB
test_100_uuquqtspuu.txt AC 34 ms 956 KB
test_100_uuvvvuvvuv.txt AC 36 ms 1140 KB
test_100_xxxyxxyyxx.txt AC 33 ms 1016 KB
test_100_zzzyyyzyyz.txt AC 35 ms 960 KB
test_15_gunspifpdv.txt AC 28 ms 980 KB
test_17_hijkabcdab.txt AC 31 ms 972 KB
test_18_ahbicjdkea.txt AC 29 ms 960 KB
test_26_codefestiv.txt AC 28 ms 960 KB
test_33_vtootzhcdu.txt AC 29 ms 1144 KB
test_72_nuauvasdgr.txt AC 30 ms 1028 KB
test_73_ftnuvdtcny.txt AC 32 ms 988 KB
test_77_ksjradlaka.txt AC 31 ms 1016 KB
test_77_txusqssdai.txt AC 34 ms 996 KB
test_83_amgctyikmg.txt AC 32 ms 964 KB
test_90_hseaevdcjj.txt AC 36 ms 1028 KB
test_93_vpywbvvvne.txt AC 32 ms 932 KB
test_94_xliaqazebk.txt AC 35 ms 960 KB
test_98_bgefabfcgb.txt AC 32 ms 1052 KB
test_98_cddabegacb.txt AC 36 ms 956 KB
test_98_cgbfcbgeed.txt AC 35 ms 956 KB
test_98_dagbdgcfbc.txt AC 34 ms 1016 KB
test_98_dbcacbabad.txt AC 33 ms 1028 KB
test_98_dffdbaabgf.txt AC 34 ms 956 KB
test_98_fdacgccfcd.txt AC 35 ms 968 KB
test_98_gagddgcegc.txt AC 35 ms 1020 KB
test_98_gbfceggdea.txt AC 31 ms 1028 KB
test_98_gddcfebeed.txt AC 32 ms 968 KB
test_a-b49.txt AC 34 ms 956 KB
test_a-b49a.txt AC 33 ms 1056 KB
test_a-b50.txt AC 39 ms 972 KB
test_a-c32.txt AC 36 ms 1144 KB
test_a-c32ab.txt AC 37 ms 960 KB
test_a-c33.txt AC 35 ms 1020 KB
test_a-c33a.txt AC 35 ms 1028 KB
test_a-pr-za-qs-z.txt AC 32 ms 1024 KB
test_a-w3yyzzyyzza-w.txt AC 34 ms 1140 KB
test_a-x2z46.txt AC 39 ms 960 KB
test_a-x2z47.txt AC 36 ms 1152 KB
test_a-x2z52.txt AC 36 ms 956 KB
test_a-xz46a-z.txt AC 33 ms 960 KB
test_a-xz47a-z.txt AC 32 ms 1052 KB
test_a-xz52a-z.txt AC 33 ms 1024 KB
test_a-yy-aa-yy-a.txt AC 34 ms 1016 KB
test_a-yy.txt AC 33 ms 1056 KB
test_a-z.txt AC 33 ms 936 KB
test_a-z3a-u.txt AC 40 ms 1036 KB
test_a-z3a-v.txt AC 47 ms 964 KB
test_a-za-z.txt AC 35 ms 1024 KB
test_a-zb-za.txt AC 33 ms 964 KB
test_a-zz-a.txt AC 33 ms 1028 KB
test_a3-z3.txt AC 33 ms 1028 KB
test_a4-y4.txt AC 35 ms 960 KB
test_a99.txt AC 35 ms 1152 KB
test_aa-y.txt AC 32 ms 960 KB
test_abababab.txt AC 28 ms 1024 KB
test_abacbabc.txt AC 31 ms 976 KB
test_abcde.txt AC 27 ms 1020 KB
test_az.txt AC 29 ms 960 KB
test_b100.txt AC 34 ms 1028 KB
test_b4-y4dkqc.txt AC 32 ms 1056 KB
test_b4-y4hhpp.txt AC 36 ms 1092 KB
test_b4-z4.txt AC 34 ms 1016 KB
test_byr.txt AC 34 ms 1020 KB
test_kxwzajmx.txt AC 46 ms 964 KB
test_pp.txt AC 30 ms 1016 KB
test_ssb4-y4ss.txt AC 33 ms 1052 KB
test_x33y33z33.txt AC 34 ms 1000 KB
test_x33y33z34.txt AC 36 ms 1048 KB
test_x33y34z33.txt AC 35 ms 960 KB
test_x34y33z33.txt AC 36 ms 1144 KB
test_z.txt AC 29 ms 972 KB
test_z98.txt AC 38 ms 952 KB