# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
158250 |
2019-10-15T18:52:29 Z |
brcode |
Miners (IOI07_miners) |
C++14 |
|
1336 ms |
245752 KB |
#include <iostream>
#include <set>
using namespace std;
const int MAXN = 2e5+5;
int dp[MAXN][5][5][5][5];
int arr[MAXN];
int query(int i,int j,int k){
set<int> s1;
if(i){
s1.insert(i);
}
if(j){
s1.insert(j);
}
if(k){
s1.insert(k);
}
// cout<<i<<" "<<j<<" "<<k<<" "<<s1.size()<<endl;
return s1.size();
}
int main(){
int n;
cin>>n;
string s;
cin>>s;
for(int i=1;i<=n;i++){
if(s[i-1] == 'M'){
arr[i] = 1;
}else if(s[i-1] == 'F'){
arr[i] = 2;
}else{
arr[i] = 3;
}
}
for(int i=0;i<=n;i++){
for(int j=0;j<=3;j++){
for(int k=0;k<=3;k++){
for(int l=0;l<=3;l++){
for(int m=0;m<=3;m++){
dp[i][j][k][l][m] = -1e9;
}
}
}
}
}
dp[0][0][0][0][0] = 0;
for(int i=1;i<=n;i++){
for(int j=0;j<=3;j++){
for(int k=0;k<=3;k++){
for(int l=0;l<=3;l++){
for(int m=0;m<=3;m++){
if(dp[i-1][j][k][l][m]!=-1e9){
dp[i][arr[i]][j][l][m] = max(dp[i][arr[i]][j][l][m],dp[i-1][j][k][l][m]+query(arr[i],j,k));
dp[i][j][k][arr[i]][l] = max(dp[i][j][k][arr[i]][l],dp[i-1][j][k][l][m]+query(arr[i],l,m));
// cout<<i<<" "<<arr[i]<<" "<<j<<" "<<l<<" "<<m<<" "<<dp[i][arr[i]][j][l][m]<<endl;
//cout<<i<<" "<<j<<" "<<k<<" "<<arr[i]<<" "<<l<<" "<<dp[i][arr[i]][j][l][m]<<endl;
}
}
}
}
}
}
int ans = 0;
for(int j=0;j<=3;j++){
for(int k=0;k<=3;k++){
for(int l=0;l<=3;l++){
for(int m=0;m<=3;m++){
ans = max(ans,dp[n][j][k][l][m]);
}
}
//ans = max(ans,dp[n][j][k]);
}
}
cout<<ans<<endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
404 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
2808 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
36 ms |
12648 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
136 ms |
24920 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
296 ms |
61712 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
633 ms |
184312 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1336 ms |
245752 KB |
Output is correct |