| Task: | Palindrome |
| Sender: | z |
| Submission time: | 2016-09-20 17:16:12 +0300 |
| Language: | C++ |
| Status: | READY |
| Result: | ACCEPTED |
| test | verdict | time | |
|---|---|---|---|
| #1 | ACCEPTED | 0.06 s | details |
| #2 | ACCEPTED | 0.05 s | details |
| #3 | ACCEPTED | 0.06 s | details |
| #4 | ACCEPTED | 0.07 s | details |
| #5 | ACCEPTED | 0.06 s | details |
| #6 | ACCEPTED | 0.06 s | details |
| #7 | ACCEPTED | 0.05 s | details |
| #8 | ACCEPTED | 0.05 s | details |
| #9 | ACCEPTED | 0.06 s | details |
| #10 | ACCEPTED | 0.05 s | details |
| #11 | ACCEPTED | 0.06 s | details |
| #12 | ACCEPTED | 0.07 s | details |
| #13 | ACCEPTED | 0.05 s | details |
| #14 | ACCEPTED | 0.06 s | details |
| #15 | ACCEPTED | 0.05 s | details |
| #16 | ACCEPTED | 0.06 s | details |
| #17 | ACCEPTED | 0.05 s | details |
| #18 | ACCEPTED | 0.06 s | details |
| #19 | ACCEPTED | 0.06 s | details |
| #20 | ACCEPTED | 0.06 s | details |
| #21 | ACCEPTED | 0.06 s | details |
| #22 | ACCEPTED | 0.05 s | details |
| #23 | ACCEPTED | 0.06 s | details |
| #24 | ACCEPTED | 0.06 s | details |
| #25 | ACCEPTED | 0.06 s | details |
| #26 | ACCEPTED | 0.06 s | details |
| #27 | ACCEPTED | 0.05 s | details |
| #28 | ACCEPTED | 0.05 s | details |
| #29 | ACCEPTED | 0.06 s | details |
| #30 | ACCEPTED | 0.06 s | details |
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 |
