oj.uz

Submission #477144

# Submission time Handle Problem Language Result Execution time Memory
477144 2021-09-30T20:59:15 Z jeroenodb Miners (IOI07_miners) C++17
100 / 100
 24 ms 588 KB 
#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 1e5+1, oo = 1e9;
const string types = "MFB";
int id(char c) {return types.find(c);}
constexpr int S=3*3;
int cmax(int& a, int b){return a=max(a,b);}
int main() {
    int n; cin >> n;
    int dp[2][S][S+1],score[S][3] = {};
    for(int i=0;i<S;++i) {
        int b = i%3, c = i/3;
        for(int j=0;j<3;++j) {
            score[i][j]+=set<int>{b,c,j}.size();
        }
    }
    for(int i=0;i<S;++i) fill(dp[0][i],dp[0][i]+S+1,-oo);
    string s; cin >> s;
    dp[0][4*id(s[0])][S]=1;
    for(int k=1;k<n;++k) {
        auto cur = dp[k%2], old = dp[(k-1)%2];
        for(int i=0;i<S;++i) fill(cur[i],cur[i]+S+1,-oo);
        int myid = id(s[k]);
        for(int i=0;i<S;++i) for(int j=0;j<=S;++j) if(old[i][j]!=-oo){
            cmax(cur[i/3+3*myid][j],old[i][j]+score[i][myid]);
            if(j==S) {
                cmax(cur[i][4*myid],old[i][j]+1);  
            } else {
                cmax(cur[i][j/3+3*myid],old[i][j]+score[j][myid]);
            }
        }
        // for(int i=0;i<S;++i) {
        //     for(int j=0;j<S;++j) {
        //         if(cur[i][j]!=-oo) {
        //             cout << setw(3) << cur[i][j];
        //         } else cout << "  *";
        //     }cout << '\n';
        // }
        // cout << "----\n";

    }
    auto cur = dp[(n-1)%2];
    int ans = -oo;
    for(int i=0;i<S;++i) ans = max(ans,*max_element(cur[i],cur[i]+S));
    cout << ans << '\n';
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 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
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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