Submission #777864

#	Time	Username	Problem	Language	Result	Execution time	Memory
777864		raysh07	Miners (IOI07_miners)	C++17	100 / 100	124 ms	100756 KiB

miners

#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 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 7 / 7
• Subtask 7: 8 / 8
• Subtask 8: 8 / 8
• Subtask 9: 8 / 8
• Subtask 10: 8 / 8
• Subtask 11: 8 / 8
• Subtask 12: 8 / 8