oj.uz

Submission #147078

# Submission time Handle Problem Language Result Execution time Memory
147078 2019-08-27T12:38:17 Z Sarah_Mokhtar Miners (IOI07_miners) C++14
100 / 100
 1455 ms 110228 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10,M=2e5+100,OO=0x3f3f3f3f,mod=1e8;
int dp[N][4][4][4][4],n;
string s;
int diff(int x, int y, int z){
    set <int> ret = {x, y, z};
    while(*ret.rbegin() == 3){
        ret.erase(--ret.end());
    }
    return ret.size();
}
int id(char c){
    if(c=='M') return 0;
    if(c=='B') return 1;
    if(c=='F') return 2;
}
int solve(int i,int pl1,int pl2,int pr1,int pr2){
    if(i==n) return 0;
    int& ret=dp[i][pl1][pl2][pr1][pr2];
    if(~ret) return ret;
    int op1=diff(pl1,pl2,id(s[i]))+solve(i+1,pl2,id(s[i]),pr1,pr2);
    int op2=diff(id(s[i]),pr1,pr2)+solve(i+1,pl1,pl2,pr2,id(s[i]));
    return ret=max(op1,op2);
}
int main(){
    cin>>n>>s;
    memset(dp,-1,sizeof(dp));
    cout<<solve(0,3,3,3,3);
}

Compilation message

miners.cpp: In function 'int id(char)':
miners.cpp:18:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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