oj.uz

Submission #1022626

# Submission time Handle Problem Language Result Execution time Memory
1022626 2024-07-13T19:41:29 Z ttamx Miners (IOI07_miners) C++17
84 / 100
 1500 ms 100912 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){
    set<int> s{a,b,c};
    s.erase(0);
    return s.size();
}

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 344 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 1 ms 348 KB Output is correct

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 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 38 ms 1372 KB Output is correct

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1607 ms 75600 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #12
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1528 ms 100912 KB Time limit exceeded
2 Halted 0 ms 0 KB -