Submission #1216871

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216871		moondarkside	Miners (IOI07_miners)	C++20	100 / 100	747 ms	112524 KiB

miners

#include<bits/stdc++.h>
using namespace std;


string S;
int n;
int transformA[]={0,1,1,2,1,2,2,3};

unordered_map<int,int> Best;

int getMax(char a,char b,int pos){
    if(S[pos]=='\0'){
        return 0;
    }
    int index=(a<<6|b)*n+pos;
    if(Best[index]!=0){
        return Best[index];
    }
    char current;
    switch(S[pos]){
        case 'M':
        current=1;
        break;
        case 'B':
        current=2;
        break;
        case 'F':
        current=4;
        break;
    }
    
    int vA=getMax(a>>3 | current<<3|current,b,pos+1)+transformA[(a|current)&7];
    
    if(a!=b){
        int vB=getMax(a,b>>3 | current<<3|current,pos+1)+transformA[(b|current)&7];
        Best[index]=max(vA,vB);
        return max(vA,vB);
    }
    
    Best[index]=vA;
    return vA;
}


int main()
{
 cin>>n>>S;

cout<<getMax(0,0,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