oj.uz

Submission #777862

# Submission time Handle Problem Language Result Execution time Memory
777862 2023-07-09T19:28:37 Z raysh07 Miners (IOI07_miners) C++17
84 / 100
 1500 ms 201056 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18

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 101 ms 200776 KB Output is correct

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1568 ms 201040 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 1571 ms 201056 KB Time limit exceeded
2 Halted 0 ms 0 KB -