oj.uz

Submission #1022629

# Submission time Handle Problem Language Result Execution time Memory
1022629 2024-07-13T19:43:54 Z ttamx Miners (IOI07_miners) C++17
100 / 100
 180 ms 100944 KB 
#include<bits/stdc++.h>

using namespace std;

const int N=1e5+5;
const int INF=INT_MAX/2;

int n;
int dp[N][4][4][4][4];
string s;
int ans;

int calc(int a,int b,int c){
    if(a==0)return (b==0||b==c)?1:2;
    if(a==b&&a==c)return 1;
    if(a==b||a==c||b==c)return 2;
    return 3;
}

void chmax(int &x,int v){
    if(v>x)x=v;
}

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n;
    cin >> s;
    for(int i=0;i<=n;i++){
        for(int x=0;x<4;x++){
            for(int y=0;y<4;y++){
                for(int z=0;z<4;z++){
                    for(int w=0;w<4;w++){
                        dp[i][x][y][z][w]=-INF;
                    }
                }
            }
        }
    }
    dp[0][0][0][0][0]=0;
    for(int i=0;i<n;i++){
        int v=s[i]=='M'?1:s[i]=='F'?2:3;
        for(int x=0;x<4;x++){
            for(int y=0;y<4;y++){
                for(int z=0;z<4;z++){
                    for(int w=0;w<4;w++){
                        chmax(dp[i+1][x][y][w][v],dp[i][x][y][z][w]+calc(z,w,v));
                        chmax(dp[i+1][y][v][z][w],dp[i][x][y][z][w]+calc(x,y,v));
                    }
                }
            }
        }
    }
    for(int x=0;x<4;x++){
        for(int y=0;y<4;y++){
            for(int z=0;z<4;z++){
                for(int w=0;w<4;w++){
                    chmax(ans,dp[n][x][y][z][w]);
                }
            }
        }
    }
    cout << ans;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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