oj.uz

Submission #1022634

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

using namespace std;

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

int n;
int dp[2][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;
}
void clear(int 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&1][x][y][z][w]=-INF;
                }
            }
        }
    }
}

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n;
    cin >> s;
    clear(0);
    dp[0][0][0][0][0]=0;
    for(int i=0;i<n;i++){
        clear(i+1);
        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^1][x][y][w][v],dp[i&1][x][y][z][w]+calc(z,w,v));
                        chmax(dp[i&1^1][y][v][z][w],dp[i&1][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&1][x][y][z][w]);
                }
            }
        }
    }
    cout << ans;
}

Compilation message

miners.cpp: In function 'int main()':
miners.cpp:48:35: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   48 |                         chmax(dp[i&1^1][x][y][w][v],dp[i&1][x][y][z][w]+calc(z,w,v));
      |                                  ~^~
miners.cpp:49:35: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   49 |                         chmax(dp[i&1^1][y][v][z][w],dp[i&1][x][y][z][w]+calc(x,y,v));
      |                                  ~^~

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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