제출 #581545

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
581545		HeyYouNotYouYou	Miners (IOI07_miners)	C++14	84 / 100	1592 ms	287216 KiB

miners

#pragma GCC optimize("O1")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 100001,INF=1e12;
int n;
string s;
//{i,{ {m1,{b1,f1}} ,{m2,{b2,f2}} }};
map<pair<int , pair<pair<int,pair<int,int>>,pair<int,pair<int,int>>>>,int>dp;
int solve(int i,int M1,int B1,int F1,int M2,int B2,int F2)
{
  //cout<<i<<" "<<M1<<" "<<B1<<" "<<F1<<" "<<M2<<" "<<B2<<" "<<F2<<endl;
  if(i==n) return 0;
  int ans=0;
  if(dp.count({i , {{M1,{B1,F1}}, {M2,{B2,F2}} }})) return dp[{i , {{M1,{B1,F1}}, {M2,{B2,F2}} }}];

  if(s[i]=='M'){
    int m1=M1,b1=B1,f1=F1;
    m1=0,b1++,f1++;
    if(B1==-1 || b1>2) b1=-1;
    if(F1==-1 || f1>2) f1=-1;
    ans = solve(i+1,m1,b1,f1,M2,B2,F2)+((m1>=0)+(b1>=0)+(f1>=0));

    m1=M2,b1=B2,f1=F2;
    m1=0,b1++,f1++;
    if(B2==-1 || b1>2) b1=-1;
    if(F2==-1 || f1>2) f1=-1;
    ans=max(ans,solve(i+1,M1,B1,F1,m1,b1,f1)+((m1>=0)+(b1>=0)+(f1>=0)));
  }
  else if(s[i]=='B'){
    int m1=M1,b1=B1,f1=F1;
    m1++,b1=0,f1++;
    if(M1==-1 || m1>2) m1=-1;
    if(F1==-1 || f1>2) f1=-1;
    ans = solve(i+1,m1,b1,f1,M2,B2,F2)+((m1>=0)+(b1>=0)+(f1>=0));

    m1=M2,b1=B2,f1=F2;
    m1++,b1=0,f1++;
    if(M2==-1 || m1>2) m1=-1;
    if(F2==-1 || f1>2) f1=-1;
    ans=max(ans,solve(i+1,M1,B1,F1,m1,b1,f1)+((m1>=0)+(b1>=0)+(f1>=0)));
  }
  else if(s[i]=='F'){
    int m1=M1,b1=B1,f1=F1;
    m1++,b1++,f1=0;
    if(M1==-1 || m1>2) m1=-1;
    if(B1==-1 || b1>2) b1=-1;
    ans = solve(i+1,m1,b1,f1,M2,B2,F2)+((m1>=0)+(b1>=0)+(f1>=0));

    m1=M2,b1=B2,f1=F2;
    m1++,b1++,f1=0;
    if(M2==-1 || m1>2) m1=-1;
    if(B2==-1 || b1>2) b1=-1;
    ans=max(ans,solve(i+1,M1,B1,F1,m1,b1,f1)+((m1>=0)+(b1>=0)+(f1>=0)));
  }
  return dp[{i , {{M1,{B1,F1}}, {M2,{B2,F2}} }}]=ans;
}
int32_t main()
{
  //freopen("abc.in", "r", stdin);
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n ;
  cin>>s;
  cout<<solve(0,-1,-1,-1,-1,-1,-1);
}

• 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: 0 / 8
• Subtask 12: 0 / 8