답안 #655337

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
655337 2022-11-03T21:07:37 Z sword060 Miners (IOI07_miners) C++17
100 / 100
358 ms 512 KB
#include <bits/stdc++.h>
using namespace std;
int x,dp[2][16][16];
string s;
int p(char c){
  if(c=='M')return 1;
  if(c=='F')return 2;
  return 3;
}
int f(int a,int b){
  int l[4],r=0;
  l[0]=0;l[1]=0;l[2]=0;l[3]=0;
  l[a&3]++;l[a>>2]++;l[b]++;
  for(int i=1;i<=3;i++)r+=(l[i]>0);
  return r;
}
int main(){
  ios::sync_with_stdio(0);cin.tie(0);
  cin>>x>>s;
  for(int i=0;i<=1;i++)
    for(int j=0;j<16;j++)
      for(int k=0;k<16;k++)
        dp[i][j][k]=-1e9;
  dp[0][0][0]=0;
  int c=0;
  for(int i=0;i<x;i++){
    for(int j=0;j<16;j++){
      for(int k=0;k<16;k++){
        int c1=f(j,p(s[i])),c2=f(k,p(s[i]));
        dp[c^1][(j>>2)|(p(s[i])<<2)][k]=max(dp[c^1][(j>>2)|(p(s[i])<<2)][k],dp[c][j][k]+c1);
        dp[c^1][j][(k>>2)|(p(s[i])<<2)]=max(dp[c^1][j][(k>>2)|(p(s[i])<<2)],dp[c][j][k]+c2);
      }
    }
    c^=1;
  }
  int ans=0;
  for(int i=0;i<16;i++)
    for(int j=0;j<16;j++)
      ans=max(ans,dp[c][i][j]);
  cout<<ans;
  return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 212 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 340 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 344 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 102 ms 340 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 293 ms 492 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 358 ms 512 KB Output is correct