oj.uz

Submission #495609

# Submission time Handle Problem Language Result Execution time Memory
495609 2021-12-19T13:07:48 Z PiejanVDC Miners (IOI07_miners) C++17
43 / 100
 1500 ms 3772 KB 
#include <bits/stdc++.h>
using namespace std;

string s;

vector<char>v,w;
int ans;

void dfs(int i) {
    if(i == s.length()) {
        int cnt = 0;
        for(int j = 0 ; j < (int)v.size()-2 ; j++) {
            //assert(j+2 < v.size());
            if(v[j] != v[j+1] && v[j] != v[j+2] && v[j+1] != v[j+2]) {
                cnt += 3;
            } else if(v[j] == v[j+1] && v[j] == v[j+2]) cnt++;
            else cnt += 2;
        }
        if(v.size() > 0) cnt++;
        if(v.size() > 1) cnt += (v[0] != v[1] ? 2 : 1);
        //cout << w.size() << " ";
        for(int j = 0 ; j < (int)w.size()-2 ; j++) {
            //assert(j+2 < w.size());
            if(w[j] != w[j+1] && w[j] != w[j+2] && w[j+1] != w[j+2]) {
                cnt += 3;
            } else if(w[j] == w[j+1] && w[j] == w[j+2]) cnt++;
            else cnt += 2;
        }
        if(w.size() > 0) cnt++;
        if(w.size() > 1) cnt += (w[0] != w[1] ? 2 : 1);
        ans = max(ans,cnt);
        return;
    }
    if(!v.empty() && v.back() != s[i] && !w.empty() && w.back() == s[i]) {
        v.push_back(s[i]);
        dfs(i+1);
        v.pop_back();
    } else if(!w.empty() && w.back() != s[i] && !v.empty() && v.back() == s[i]) {
        w.push_back(s[i]);
        dfs(i+1);
        w.pop_back();
    } else {
        v.push_back(s[i]);
        dfs(i+1);
        v.pop_back();
        w.push_back(s[i]);
        dfs(i+1);
        w.pop_back();
    }
}

signed main() {
    int n; cin>>n;
    cin>>s;
    dfs(0);
    cout << ans;
}

Compilation message

miners.cpp: In function 'void dfs(int)':
miners.cpp:10:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     if(i == s.length()) {
      |        ~~^~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1031 ms 276 KB Output is correct

Subtask #7
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1583 ms 204 KB Time limit exceeded

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1590 ms 460 KB Time limit exceeded

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1577 ms 588 KB Time limit exceeded

Subtask #10
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1589 ms 1100 KB Time limit exceeded

Subtask #11
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1532 ms 2896 KB Time limit exceeded

Subtask #12
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1587 ms 3772 KB Time limit exceeded