oj.uz

Submission #777864

# Submission time Handle Problem Language Result Execution time Memory
777864 2023-07-09T19:32:14 Z raysh07 Miners (IOI07_miners) C++17
100 / 100
 124 ms 100756 KB 
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define INF (int)1e9

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

const int N = 1e5 + 69;
int n;
int dp[N][4][4][4][4]; //states of previous 2
int prec[4][4][4];

int f(int x, int y, int z){
	return prec[x][y][z];
}

void Solve()
{
	for (int x = 0; x < 4; x++){
		for (int y = 0; y < 4; y++){
			for (int z = 0; z < 4; z++){
				set <int> st;
				st.insert(x); st.insert(y); st.insert(z);
				st.erase(0);
				prec[x][y][z] = st.size();
			}
		}
	}

	cin >> n;
	string s; cin >> s;
	for (int i = 0; i < N; i++){
		for (int j = 0; j < 4; j++){
			for (int k = 0; k < 4; k++){
				for (int l = 0; l < 4; l++){
					for (int m = 0; m < 4; m++){
						dp[i][j][k][l][m] = -INF;
						if (i + j + k + l + m == 0) dp[i][j][k][l][m] = 0;
					}
				}
			}
		}
	}

	s = "0" + s;

	for (int i = 1; i <= n; i++){
		int x;
		if (s[i] == 'M') x = 1;
		else if (s[i] == 'B') x = 2;
		else x = 3;

		for (int i1 = 0; i1 < 4; i1++){
			for (int i2 = 0; i2 < 4; i2++){
				for (int j1 = 0; j1 < 4; j1++){
					for (int j2 = 0; j2 < 4; j2++){
						int y = dp[i - 1][i1][i2][j1][j2];
						dp[i][x][i1][j1][j2] = max(dp[i][x][i1][j1][j2], y + f(x, i1, i2));
						dp[i][i1][i2][x][j1] = max(dp[i][i1][i2][x][j1], y + f(x, j1, j2));
					}
				}
			}
		}
	}

	int ans = 0;

	for (int i = 0; i < N; i++){
		for (int j = 0; j < 4; j++){
			for (int k = 0; k < 4; k++){
				for (int l = 0; l < 4; l++){
					for (int m = 0; m < 4; m++){
						ans = max(ans, dp[i][j][k][l][m]);
					}
				}
			}
		}
	}

	cout << ans << "\n";
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    
  //  cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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