| Task: | ABC-poisto |
| Sender: | rasastusni |
| Submission time: | 2020-10-17 23:06:52 +0300 |
| Language: | C++ (C++17) |
| Status: | READY |
| Result: | 42 |
| group | verdict | score |
|---|---|---|
| #1 | ACCEPTED | 42 |
| #2 | TIME LIMIT EXCEEDED | 0 |
| test | verdict | time | group | |
|---|---|---|---|---|
| #1 | ACCEPTED | 0.01 s | 1, 2 | details |
| #2 | TIME LIMIT EXCEEDED | -- | 2 | details |
Compiler report
input/code.cpp: In function 'int slow(const string&)':
input/code.cpp:13:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < s.size() - 1; ++i) {
~~^~~~~~~~~~~~~~Code
#include <iostream>
#include <map>
#include <string>
using namespace std;
map<string, int> cache;
int slow(const string &s) {
if (s.size() == 0) return 0;
if (cache.find(s) != cache.end()) return cache[s];
int maxways = 0;
for (int i = 0; i < s.size() - 1; ++i) {
if (s[i] != s[i+1]) {
string s2 = s;
s2.erase(i, 2);
maxways = max(maxways, slow(s2) + 2);
}
}
cache[s] = maxways;
return maxways;
}
int main()
{
int t;
cin >> t;
for (int i = 0; i < t; ++i) {
string s;
cin >> s;
cout << slow(s) << endl;
}
}