oj.uz

Submission #777863

# Submission time Handle Problem Language Result Execution time Memory
777863 2023-07-09T19:29:24 Z raysh07 Miners (IOI07_miners) C++17
84 / 100
 1500 ms 100684 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 f(int x, int y, int z){
	set <int> st;
	st.insert(x); st.insert(y); st.insert(z);
	st.erase(0);
	return st.size();
}

void Solve()
{
	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 67 ms 100560 KB Output is correct

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1562 ms 100684 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 1565 ms 100684 KB Time limit exceeded
2 Halted 0 ms 0 KB -