제출 #533608

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
533608		groshi	Miners (IOI07_miners)	C++17	100 / 100	490 ms	374484 KiB

miners

#include<iostream>
#include<map>
using namespace std;
int dp[100005][3][3][3][3][3][3];
bool odw[100005][3][3][3][3][3][3];
map<char,int> mapka;
int kub[3];
int n;
string s;
int reku(int i,int x1,int x2,int ile1,int y1,int y2,int ile2)
{
    if(i==n+1)
        return 0;
    if(odw[i][x1][x2][ile1][y1][y2][ile2])
        return dp[i][x1][x2][ile1][y1][y2][ile2];
    odw[i][x1][x2][ile1][y1][y2][ile2]=1;
    if(ile1>=1)
        kub[x1]=1;
    if(ile1>=2)
        kub[x2]=1;
    kub[mapka[s[i]]]=1;
    int mam=kub[0]+kub[1]+kub[2];
    kub[0]=0;
    kub[1]=0;
    kub[2]=0;
    dp[i][x1][x2][ile1][y1][y2][ile2]=max(dp[i][x1][x2][ile1][y1][y2][ile2],reku(i+1,mapka[s[i]],x1,min(ile1+1,2),y1,y2,ile2)+mam);

    if(ile2>=1)
        kub[y1]=1;
    if(ile2>=2)
        kub[y2]=1;
    kub[mapka[s[i]]]=1;
    mam=kub[0]+kub[1]+kub[2];
    kub[0]=0;
    kub[1]=0;
    kub[2]=0;
    dp[i][x1][x2][ile1][y1][y2][ile2]=max(dp[i][x1][x2][ile1][y1][y2][ile2],reku(i+1,x1,x2,ile1,mapka[s[i]],y1,min(ile2+1,2))+mam);
    return dp[i][x1][x2][ile1][y1][y2][ile2];
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    cin>>s;
    s="0"+s;
    mapka['M']=0;
    mapka['B']=1;
    mapka['F']=2;
    cout<<reku(1,0,0,0,0,0,0);
    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