oj.uz

Submission #655336

# Submission time Handle Problem Language Result Execution time Memory
655336 2022-11-03T21:02:23 Z sword060 Miners (IOI07_miners) C++17
100 / 100
 286 ms 111668 KB 
#include <bits/stdc++.h>
using namespace std;
int x,dp[100005][16][16];
map<char,int>mp;
string s;
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 rec(int i,int l,int r){
  if(i==x)return 0;
  if(~dp[i][l][r])return dp[i][l][r];
  int c1=f(l,mp[s[i]]),c2=f(r,mp[s[i]]);
  return dp[i][l][r]=max(rec(i+1,(l>>2)|(mp[s[i]]<<2),r)+c1,rec(i+1,l,(r>>2)|(mp[s[i]]<<2))+c2);
}
int main(){
  ios::sync_with_stdio(0);cin.tie(0);
  memset(dp,-1,sizeof(dp));
  mp['M']=1;mp['F']=2;mp['B']=3;
  cin>>x>>s;
  cout<<rec(0,0,0);
  return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 100468 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 100496 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 100500 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 100452 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 100432 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 100380 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 100544 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 101028 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 101612 KB Output is correct

Subtask #10
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 103280 KB Output is correct

Subtask #11
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 108900 KB Output is correct

Subtask #12
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 111668 KB Output is correct