Submission #970818

#	Time	Username	Problem	Language	Result	Execution time	Memory
970818		Ludissey	Miners (IOI07_miners)	C++17	100 / 100	795 ms	444772 KiB

miners

#include <bits/stdc++.h>
#define sz(a) (int)a.size()
#define all(x) (x).begin(), (x).end()
using namespace std;
vector<int> a;
vector<vector<vector<vector<vector<int>>>>> memo;

int calcExtra(int c, int prev, int prev2){
    if(prev==3) return 1;
    else if(prev2==3){
        if(prev!=c) return 2;
        else return 1;
    }
    if(c!=prev&&prev2!=c&&prev2!=prev) return 3;
    else if(c==prev&&prev2==c) return 1;
    else return 2;
}

int dp(int x, int prev, int prevprev, int prev2, int prevprev2){
    if(x==sz(a)) return 0;
    if(memo[x][prev][prevprev][prev2][prevprev2]!=-1) return memo[x][prev][prevprev][prev2][prevprev2];
    int mine1=dp(x+1,a[x], prev ,prev2,prevprev2)+calcExtra(a[x],prev,prevprev);
    int mine2=dp(x+1,prev,prevprev, a[x], prev2)+calcExtra(a[x],prev2,prevprev2);
    return memo[x][prev][prevprev][prev2][prevprev2]=max(mine1,mine2);
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int n; cin >> n;
    a.resize(n);
    memo.resize(n+1, vector<vector<vector<vector<int>>>>(4,vector<vector<vector<int>>>(4, vector<vector<int>>(4, vector<int>(4, -1)))));
    for (int i = 0; i < n; i++) 
    {
        char c; cin >>c;
        if(c=='M') a[i]=0;
        else if(c=='B') a[i]=1;
        else if(c=='F') a[i]=2;
    }
    cout << dp(0,3,3,3,3)<<"\n";
    return 0;
}

• 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