Submission #477144

#	Time	Username	Problem	Language	Result	Execution time	Memory
477144		jeroenodb	Miners (IOI07_miners)	C++17	100 / 100	24 ms	588 KiB

miners

#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 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 7 / 7
• Subtask 7: 8 / 8
• Subtask 8: 8 / 8
• Subtask 9: 8 / 8
• Subtask 10: 8 / 8
• Subtask 11: 8 / 8
• Subtask 12: 8 / 8