oj.uz

Submission #65135

# Submission time Handle Problem Language Result Execution time Memory
65135 2018-08-06T17:10:56 Z edisonhello Miners (IOI07_miners) C++14
100 / 100
 77 ms 1124 KB 
#include<bits/stdc++.h>
using namespace std;

int produce[27];
int dp[3][9][9];

int main(){
    int n; cin>>n;
    string s; cin>>s;
    for(char &c:s){
        if(c=='M')c=0;
        else if(c=='B')c=1;
        else c=2;
    }
    s='z'+s;
    for(int i=0;i<3;++i)for(int j=0;j<3;++j)for(int k=0;k<3;++k){
        set<int> st; st.insert(i); st.insert(j); st.insert(k);
        produce[i*9+j*3+k]=st.size();
        // cout<<i<<" "<<j<<" "<<k<<" "<<st.size()<<endl;
    }
    for(int i=1;i<=n;++i){
        for(int j=0;j<9;++j){
            for(int k=0;k<9;++k){
#define up(a,b) a=max(a,b)
                up(dp[i&1][(j*3+s[i])%9][k],dp[(i-1)&1][j][k]+produce[j*3+s[i]]);
                up(dp[i&1][j][(k*3+s[i])%9],dp[(i-1)&1][j][k]+produce[k*3+s[i]]);
            }
        }
    }
    int mx=0;
    for(int j=0;j<9;++j)for(int k=0;k<9;++k){
        mx=max(mx,dp[n&1][j][k]);
    }
    cout<<mx-6<<endl;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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