oj.uz

Submission #581528

# Submission time Handle Problem Language Result Execution time Memory
581528 2022-06-22T17:32:48 Z HeyYouNotYouYou Miners (IOI07_miners) C++14
76 / 100
 1500 ms 252432 KB 
#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);
  cin >> n ;
  cin>>s;
  cout<<solve(0,-1,-1,-1,-1,-1,-1);
}

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 8108 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 11468 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 686 ms 100064 KB Output is correct

Subtask #10
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1556 ms 199584 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #11
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1584 ms 241716 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #12
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1589 ms 252432 KB Time limit exceeded
2 Halted 0 ms 0 KB -