Submission #237463

#	Time	Username	Problem	Language	Result	Execution time	Memory
237463		nikatamliani	Miners (IOI07_miners)	C++14	100 / 100	108 ms	628 KiB

miners

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 1;
int dp[2][4][4][4][4], ans = 0;
string s;
int diff(int t1, int t2, int t3){
	bool f[4] = {0, 0, 0, 0}; 
	f[t1] = f[t2] = f[t3] = 1;
	return f[1] + f[2] + f[3]; 
}
int main(){
	memset(dp, -1, sizeof dp);
	dp[0][0][0][0][0] = 0;
	int n;
	string s;
	cin >> n >> s;
	s = "@" + s;
	for(int i = 1; i <= n; ++i){
		int t = 1;
		if(s[i] == 'B')t = 2;
		if(s[i] == 'F')t = 3;
		for(int t0 = 0; t0 < 4; ++t0){
			for(int t1 = 0; t1 < 4; ++t1){
				for(int T0 = 0; T0 < 4; ++T0){
					for(int T1 = 0; T1 < 4; ++T1){
						int &dp0 = dp[1][t1][t][T0][T1];
						int &dp1 = dp[1][t0][t1][T1][t];
						int opt = dp[0][t0][t1][T0][T1];
						if(~opt){
							dp0 = max(dp0, opt + diff(t0, t1, t));
							dp1 = max(dp1, opt + diff(T0, T1, t));
						}
					}
				}
			}
		}
		for(int t0 = 0; t0 < 4; ++t0){
			for(int t1 = 0; t1 < 4; ++t1){
				for(int T0 = 0; T0 < 4; ++T0){
					for(int T1 = 0; T1 < 4; ++T1){
						dp[0][t0][t1][T0][T1] = dp[1][t0][t1][T0][T1];
						dp[1][t0][t1][T0][T1] = -1;
					}
				}
			}
		}
	}
	for(int t0 = 0; t0 < 4; ++t0){
		for(int t1 = 0; t1 < 4; ++t1){
			for(int T0 = 0; T0 < 4; ++T0){
				for(int T1 = 0; T1 < 4; ++T1){
					ans = max(ans, dp[0][t0][t1][T0][T1]);
				}
			}
		}
	}
	cout << ans << endl;
}

• 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