oj.uz

Submission #851526

# Submission time Handle Problem Language Result Execution time Memory
851526 2023-09-20T03:52:43 Z abcvuitunggio Miners (IOI07_miners) C++17
100 / 100
 644 ms 113848 KB 
#include <bits/stdc++.h>
using namespace std;
int n,a[100001],dp[100001][4][4][4][4];
string s;
set <int> sl,sr;
int f(int i, int j, int k, int l, int m){
    if (i>n)
        return 0;
    if (dp[i][j][k][l][m]!=-1)
        return dp[i][j][k][l][m];
    sl.clear();
    sr.clear();
    if (j)
        sl.insert(j);
    if (k)
        sl.insert(k);
    if (l)
        sr.insert(l);
    if (m)
        sr.insert(m);
    sl.insert(a[i]);
    sr.insert(a[i]);
    int x=sl.size(),y=sr.size();
    return dp[i][j][k][l][m]=max(f(i+1,k,a[i],l,m)+x,f(i+1,j,k,m,a[i])+y);
}
int main(){
    ios_base::sync_with_stdio(NULL);cin.tie(nullptr);
    cin >> n >> s;
    for (int i=1;i<=n;i++)
        a[i]=(s[i-1]=='M'?1:s[i-1]=='F'?2:3);
    memset(dp,-1,sizeof(dp));
    cout << f(1,0,0,0,0);
}

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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