제출 #1066764

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1066764		Muhammet	Miners (IOI07_miners)	C++17	9 / 100	1553 ms	1240 KiB

miners

#include <bits/stdc++.h>

using namespace std;

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

const int N = 200005;

int n;

string s;

map <char, int> m;

map <int,bool> m1;

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.clear();
						int k = 0;
                        m1[0] = 1;
						if(m1.find(a1) == m1.end()) k++, m1[a1] = 1;
						if(m1.find(a2) == m1.end()) k++, m1[a2] = 1;
						if(m1.find(a[i]) == m1.end()) k++, m1[a[i]] = 1;
						if(a2 == 0){
							dp[1][a1][a[i]][b1][b2] = dp[0][a1][a2][b1][b2] + k;
						}
						else {
							dp[1][a2][a[i]][b1][b2] = dp[0][a1][a2][b1][b2] + k;
						}
						k = 0;
						m1.clear();
                        m1[0] = 1;
						if(m1.find(b1) == m1.end()) k++, m1[b1] = 1;
						if(m1.find(b2) == m1.end()) k++, m1[b2] = 1;
						if(m1.find(a[i]) == m1.end()) k++, m1[a[i]] = 1;
						if(b2 == 0){
							dp[1][a1][a2][b1][a[i]] = dp[0][a1][a2][b1][b2] + k;
						}
						else {
							dp[1][a1][a2][b2][a[i]] = dp[0][a1][a2][b1][b2] + k;
						}
					}
				}
			}
		}
		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: 0 / 9
• Subtask 3: 0 / 9
• Subtask 4: 0 / 9
• Subtask 5: 0 / 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