Submission #1066865

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066865		Muhammet	Miners (IOI07_miners)	C++17	100 / 100	153 ms	1240 KiB

miners

#include <bits/stdc++.h>

using namespace std;

#define sz(s) (int)s.size()

const int N = 200005;

int n;

bool m1[10];

string s;

map <char, int> m;

int main(){
	cin >> n >> s;
	vector <int> a;
	vector <vector <vector <vector <vector<int>>>>> dp(2, vector <vector <vector<vector <int>>>> (4, vector <vector<vector <int>>> (4, vector<vector <int>> (4, vector <int> (4,-1)))));
	int cnt = 0;
	for(int i = 0; i < n; i++){
		if(m.find(s[i]) == m.end()){
			cnt++;
			m[s[i]] = cnt;
		}
		a.push_back(m[s[i]]);
	}
	dp[0][0][0][0][0] = 0;
	for(int i = 0; i < n; i++){
		for(int a1 = 0; a1 < 4; a1++){
			for(int a2 = 0; a2 < 4; a2++){
				for(int b1 = 0; b1 < 4; b1++){
					for(int b2 = 0; b2 < 4; b2++){
						if(dp[0][a1][a2][b1][b2] == -1) continue;
						m1[1] = m1[2] = m1[3] = 0;
						int k = 0;
                        m1[0] = 1;
						if(m1[a1] == 0) k++, m1[a1] = 1;
						if(m1[a2] == 0) k++, m1[a2] = 1;
						if(m1[a[i]] == 0) k++, m1[a[i]] = 1;
						if(a1 == 0){
							dp[1][a[i]][a2][b1][b2] = max(dp[0][a1][a2][b1][b2] + k, dp[1][a[i]][a2][b1][b2]);
						}
						else if(a2 == 0){
							dp[1][a1][a[i]][b1][b2] = max(dp[0][a1][a2][b1][b2] + k, dp[1][a1][a[i]][b1][b2]);
						}
						else {
							dp[1][a2][a[i]][b1][b2] = max(dp[0][a1][a2][b1][b2] + k, dp[1][a2][a[i]][b1][b2]);
						}
						k = 0;
						m1[1] = m1[2] = m1[3] = 0;
                        m1[0] = 1;
						if(m1[b1] == 0) k++, m1[b1] = 1;
						if(m1[b2] == 0) k++, m1[b2] = 1;
						if(m1[a[i]] == 0) k++, m1[a[i]] = 1;
						if(b1 == 0){
							dp[1][a1][a2][a[i]][b2] = max(dp[0][a1][a2][b1][b2] + k, dp[1][a1][a2][a[i]][b2]);
						}
						else if(b2 == 0){
							dp[1][a1][a2][b1][a[i]] = max(dp[0][a1][a2][b1][b2] + k, dp[1][a1][a2][b1][a[i]]);
						}
						else {
							dp[1][a1][a2][b2][a[i]] = max(dp[0][a1][a2][b1][b2] + k, dp[1][a1][a2][b2][a[i]]);
						}
					}
				}
			}
		}
		dp[0] = dp[1];
	}
	int ans = 0;
	for(int a1 = 0; a1 < 4; a1++){
		for(int a2 = 0; a2 < 4; a2++){
			for(int b1 = 0; b1 < 4; b1++){
				for(int b2 = 0; b2 < 4; b2++){
					ans = max(ans,dp[0][a1][a2][b1][b2]);
				}
			}
		}
	}
	cout << ans << '\n';
}

• 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