Submission #1156254

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156254		Alihan_8	Miners (IOI07_miners)	C++20	100 / 100	377 ms	636 KiB

miners

#include <bits/stdc++.h>

using namespace std;

const int inf = 1e8;

int pw[5] = {1, 4, 16, 64, 256};

void chmax(int &x, const int &y){ x = max(x, y); }

signed main(){
	int n; cin >> n;
	
	string s; cin >> s;
	
	for ( auto &x: s ){
		if ( x == 'M' ) x = 0;
		else if ( x == 'F' ) x = 1;
		else x = 2;
	}
	
	auto get = [&](int x, int y, int z){
		set <int> st;
		
		for ( auto i: {x, y, z} ){
			if ( i < 3 ) st.insert(i);
		}
		
		return st.size();
	};
	
	vector <int> dp(256, -inf);
	
	dp[255] = 0;
	
	for ( auto &v: s ){
		vector <int> nxt(256, -inf);
		
		for ( int i = 0; i < 256; i++ ){
			if ( dp[i] < 0 ) continue;
			
			{
				int x = i / pw[0] % 4, y = i / pw[1] % 4;
				 
				chmax(nxt[i - x - y * pw[1] + y + v * pw[1]], dp[i] + get(x, y, v));
			}
			{
				int x = i / pw[2] % 4, y = i / pw[3] % 4;
				
				chmax(nxt[i - x * pw[2] - y * pw[3] + y * pw[2] + v * pw[3]], dp[i] + get(x, y, v));
			}
		}
		
		swap(dp, nxt);
	}
	
	cout << *max_element(dp.begin(), dp.end()) << '\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