oj.uz

Submission #1011340

# Submission time Handle Problem Language Result Execution time Memory
1011340 2024-06-30T11:07:19 Z kaopj Miners (IOI07_miners) C++17
68 / 100
 1500 ms 344976 KB 
#include <iostream>
#include <vector>
#include <map>
#define lgm cin.tie(0)->sync_with_stdio(0);
using namespace std;
#define int long long
signed main() {
    lgm;
    int n;
    cin >> n;
    string c;
    cin >> c;
    map<tuple<int,vector<char>,vector<char>>,int> dp;
    auto dfs = [&] (auto dfs,int p,vector<char> a,vector<char> b)->int {
        if (dp[{p,a,b}] != 0) {
            return dp[{p,a,b}];
        }
        vector<char> ua=a,ub=b;
        int sa=0,sb=0;
        bool hm=0,hb=0,hf=0;
        ua[0]=ua[1];
        ua[1]=ua[2];
        ua[2]=c[p];
        ub[0]=ub[1];
        ub[1]=ub[2];
        ub[2]=c[p];
        for (int i=0;i<3;i++) {
            if (ua[i] == 'M') {
                sa+=1-hm;
                hm=1;
            } else if (ua[i] == 'B') {
                sa+=1-hb;
                hb=1;
            } else if (ua[i] == 'F') {
                sa+=1-hf;
                hf=1;
            }
        }
        hm=0; hb=0; hf=0;
        for (int i=0;i<3;i++) {
            if (ub[i] == 'M') {
                sb+=1-hm;
                hm=1;
            } else if (ub[i] == 'B') {
                sb+=1-hb;
                hb=1;
            } else if (ub[i] == 'F') {
                sb+=1-hf;
                hf=1;
            }
        }
        if (p == n-1) {
            return dp[{p,a,b}]=max(sa,sb);
        }
        return dp[{p,a,b}]=max(sa+dfs(dfs,p+1,ua,b),sb+dfs(dfs,p+1,a,ub));
    };
    cout << dfs(dfs,0,{' ',' ',' '},{' ',' ',' '});
    return 0;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1567 ms 287968 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1550 ms 307964 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #11
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1542 ms 325860 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #12
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1554 ms 344976 KB Time limit exceeded
2 Halted 0 ms 0 KB -