CSES - Putka Open 2020 – 3/5 - Results
Submission details
Task:ABC-poisto
Sender:kluopaja
Submission time:2020-10-18 20:02:23 +0300
Language:C++ (C++11)
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED42
#2ACCEPTED58
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2details
#2ACCEPTED0.01 s2details

Compiler report

input/code.cpp: In function 'int solve(std::__cxx11::string)':
input/code.cpp:14:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i+1 < s.size(); ++i) {
                  ~~~~^~~~~~~~~~
input/code.cpp:20:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 3; i <= s.size(); ++i) {
                  ~~^~~~~~~~~~~
input/code.cpp:22:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = 0; i+j <= s.size(); ++j) {
                    ~~~~^~~~~~~~~~~
input/code.cpp:45:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 1; i <= s.size(); ++i) {
                  ~~^~~~~~~~~~~

Code

#include <iostream>
#include <cstring>
#include <string>
using namespace std;
// CCAAABBBAA
//
const int N_MAX = 101;
// length of the segment, start of the segment
int dp1[N_MAX][N_MAX];
int dp2[N_MAX];
int solve(string s) {
memset(dp1, 0, sizeof(dp1));
memset(dp2, 0, sizeof(dp2));
for(int i = 0; i+1 < s.size(); ++i) {
if(s[i] != s[i+1]) {
dp1[2][i] = 1;
}
}
// i is the length of the segment
for(int i = 3; i <= s.size(); ++i) {
// j is the start of the segment
for(int j = 0; i+j <= s.size(); ++j) {
if(dp1[i-2][j+1] && s[j] != s[j+i-1]) {
dp1[i][j] = 1;
}
else {
for(int k = 2; k+2 <= i; ++k) {
if(dp1[k][j] && dp1[i-k][j+k]) {
dp1[i][j] = 1;
break;
}
}
}
}
}
/*
for(int i = 0; i < s.size(); ++i) {
for(int j = 0; j <= s.size(); ++j) {
cout<<i<<' '<<j<<' '<<dp1[j][i]<<'\n';
}
}
*/
// dp2[i] == the amount of characters that can
// be removed from 0...i-1
for(int i = 1; i <= s.size(); ++i) {
dp2[i] = dp2[i-1];;
for(int j = 0; j + 2 <= i; ++j) {
if(dp1[i-j][j]) {
dp2[i] = max(dp2[i], dp2[j] + i-j);
}
}
}
return dp2[s.size()];
}
int main() {
int tt;
cin>>tt;
for(int xx = 0; xx < tt; ++xx) {
string s;
cin>>s;
int ans = solve(s);
cout<<ans<<endl;
}
}

Test details

Test 1

Group: 1, 2

Verdict: ACCEPTED

input
100
CABC
BABCCBCA
CBBCBBAC
ACAA
...

correct output
4
8
8
2
2
...

user output
4
8
8
2
2
...
Truncated

Test 2

Group: 2

Verdict: ACCEPTED

input
100
CCAAACBCBBCCACBBBCCACCCBABBCAB...

correct output
48
4
4
96
70
...

user output
48
4
4
96
70
...
Truncated