oj.uz

Submission #1011379

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

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 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 169 ms 25312 KB Output is correct

Subtask #8
8.0 / 8.0

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

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1537 ms 273636 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 1536 ms 269076 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 1577 ms 311656 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 1572 ms 322460 KB Time limit exceeded
2 Halted 0 ms 0 KB -