Submission #1147091

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147091		Tsagana	Miners (IOI07_miners)	C++20	45 / 100	1603 ms	217336 KiB

miners

#include<bits/stdc++.h>

#define IOS ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define all(x) x.begin(), x.end()
#define int long long
#define pq priority_queue
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pp pop_back
#define F first
#define S second

using namespace std;

int n;
string s;
int a[100010];
int dp[100010][4][4][4][4];

int val(vector<int> v) {
	set<int> t;
	for (auto i: v) if (i) t.insert(i);
	return t.size();
}

int calc(int i, int a1, int a2, int b1, int b2) {
	if (i == n) return 0;
	int res = dp[i][a1][a2][b1][b2];
	if (~res) return res;
	int x = val({a1, a2, a[i]}), y = val({b1, b2, a[i]});
	return max(calc(i+1, a[i], a1, b1, b2) + x, calc(i+1, a1, a2, a[i], b1) + y);
}

signed main() {
	IOS
	memset(dp, -1, sizeof dp);
	cin >> n >> s;
	for (int i = 0; i < n; i++) a[i] = (s[i] == 'M' ? 1 : (s[i] == 'B' ? 2 : 3));
	cout << calc(0, 0, 0, 0, 0);
	return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 0 / 7
• Subtask 7: 0 / 8
• Subtask 8: 0 / 8
• Subtask 9: 0 / 8
• Subtask 10: 0 / 8
• Subtask 11: 0 / 8
• Subtask 12: 0 / 8