CSES - KILO 2016 3/5 - Results
Submission details
Task:Palindrome
Sender:z
Submission time:2016-09-20 17:16:12 +0300
Language:C++
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.06 sdetails
#2ACCEPTED0.05 sdetails
#3ACCEPTED0.06 sdetails
#4ACCEPTED0.07 sdetails
#5ACCEPTED0.06 sdetails
#6ACCEPTED0.06 sdetails
#7ACCEPTED0.05 sdetails
#8ACCEPTED0.05 sdetails
#9ACCEPTED0.06 sdetails
#10ACCEPTED0.05 sdetails
#11ACCEPTED0.06 sdetails
#12ACCEPTED0.07 sdetails
#13ACCEPTED0.05 sdetails
#14ACCEPTED0.06 sdetails
#15ACCEPTED0.05 sdetails
#16ACCEPTED0.06 sdetails
#17ACCEPTED0.05 sdetails
#18ACCEPTED0.06 sdetails
#19ACCEPTED0.06 sdetails
#20ACCEPTED0.06 sdetails
#21ACCEPTED0.06 sdetails
#22ACCEPTED0.05 sdetails
#23ACCEPTED0.06 sdetails
#24ACCEPTED0.06 sdetails
#25ACCEPTED0.06 sdetails
#26ACCEPTED0.06 sdetails
#27ACCEPTED0.05 sdetails
#28ACCEPTED0.05 sdetails
#29ACCEPTED0.06 sdetails
#30ACCEPTED0.06 sdetails

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:19:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=0; i<s.size(); ++i){
                          ^
input/code.cpp:24:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=1; i<s.size(); ++i){
                          ^
input/code.cpp:34:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i=0; i<s.size(); ++i){
                          ^
input/code.cpp:36:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (i<s.size()-1){
                    ^

Code

#include <iostream>
using namespace std;



int dp[2020][2020];


int main(){
  string s;
  cin >> s;
  
  bool si=0;
  for (int j=s.size()-1; j>=0; --j){
    si=(si || (s[j]==s[0]));
    dp[0][j]=s.size()-j-si;
  }
  si=0;
  for (int i=0; i<s.size(); ++i){
    si=(si || (s[i]==s[s.size()-1]));
    dp[i][s.size()-1]=i+1-si;
  }
  
  for (int i=1; i<s.size(); ++i){
    for (int j=s.size()-2; j>=i; --j){
      if (s[i]==s[j]) dp[i][j]=dp[i-1][j+1];
      else{
	dp[i][j]=min(dp[i-1][j+1]+1, min(dp[i-1][j]+1, dp[i][j+1]+1));
      }
    }
  }
  
  int ans=1222333444;
  for (int i=0; i<s.size(); ++i){
    ans=min(ans, dp[i][i]);
    if (i<s.size()-1){
      ans=min(ans, dp[i][i+1]);
    }
  }
  cout << ans << "\n";
}

Test details

Test 1

Verdict: ACCEPTED

input
ulfoeirkeoqdqodoogghreatbunekn...

correct output
322

user output
322

Test 2

Verdict: ACCEPTED

input
pdloqnpaoipdormtocrkbugqkutggo...

correct output
42

user output
42

Test 3

Verdict: ACCEPTED

input
nsjeeqtgbhihbqnrkjqesndoqpsupm...

correct output
6

user output
6

Test 4

Verdict: ACCEPTED

input
cbdabbabdadbddccdabbddbbabdbcb...

correct output
520

user output
520

Test 5

Verdict: ACCEPTED

input
qufflsdamkhaqfstkpmggbiscqahmb...

correct output
332

user output
332

Test 6

Verdict: ACCEPTED

input
metqijcfsonpgtjkgfnbkkcmhfdidr...

correct output
52

user output
52

Test 7

Verdict: ACCEPTED

input
gjctsgogicncablbpicjhhhtumcqcr...

correct output
7

user output
7

Test 8

Verdict: ACCEPTED

input
bcdaccdaaaddbddbcbabccbabbcadd...

correct output
517

user output
517

Test 9

Verdict: ACCEPTED

input
ljqskggebsriqfcrbaseostkbtufpk...

correct output
323

user output
323

Test 10

Verdict: ACCEPTED

input
opthatefgdoqcnelkocdpiekdalblk...

correct output
43

user output
43

Test 11

Verdict: ACCEPTED

input
tsifskqoacandopustasbcprqqgubc...

correct output
9

user output
9

Test 12

Verdict: ACCEPTED

input
dcdcddcaccccccbddabadacadaadad...

correct output
519

user output
519

Test 13

Verdict: ACCEPTED

input
psmqpkpdbflqsnummddslbbmqlbttl...

correct output
344

user output
344

Test 14

Verdict: ACCEPTED

input
kfbicrmensbkppfnechdgaangnekra...

correct output
47

user output
47

Test 15

Verdict: ACCEPTED

input
utmicheffpsumjmdmlltfkauerouou...

correct output
7

user output
7

Test 16

Verdict: ACCEPTED

input
aadcbccaddbbddaacdacbadcccccab...

correct output
513

user output
513

Test 17

Verdict: ACCEPTED

input
knousbhjpartmqrddgtuilrqmptfbm...

correct output
347

user output
347

Test 18

Verdict: ACCEPTED

input
mialfaqdecpampccjljbtfcsobdumg...

correct output
50

user output
50

Test 19

Verdict: ACCEPTED

input
tbolpoikroedjdrjqboqptktnqfulo...

correct output
15

user output
15

Test 20

Verdict: ACCEPTED

input
babbbabcacbbbdcaacddadaaadccdc...

correct output
521

user output
521

Test 21

Verdict: ACCEPTED

input
oqbbmemeheigflklkicqdlriifijfp...

correct output
350

user output
350

Test 22

Verdict: ACCEPTED

input
iscgirlmkcdgisciganitjdugeoegb...

correct output
45

user output
45

Test 23

Verdict: ACCEPTED

input
nrlifhnrkorbihsosdibeaapnbcmnp...

correct output
10

user output
10

Test 24

Verdict: ACCEPTED

input
ddbdcacbacadaaaaddcaadbdcabbba...

correct output
524

user output
524

Test 25

Verdict: ACCEPTED

input
pskpisphqttuafltbrgiliehohrdre...

correct output
301

user output
301

Test 26

Verdict: ACCEPTED

input
qlmpbmdcjgiibjdggepnjgdqddrjgu...

correct output
42

user output
42

Test 27

Verdict: ACCEPTED

input
kmemgrjpooulrgoofbejhtfnsdpfnl...

correct output
5

user output
5

Test 28

Verdict: ACCEPTED

input
dbadbacabbaabccdbcacdadbaddcca...

correct output
523

user output
523

Test 29

Verdict: ACCEPTED

input
riucascnslqgplsknhpmccgqenhpni...

correct output
357

user output
357

Test 30

Verdict: ACCEPTED

input
dedhqdrbrorasgunkdtdsujciuaqbu...

correct output
48

user output
48