Submission #730846

#	Time	Username	Problem	Language	Result	Execution time	Memory
730846		NintsiChkhaidze	Miners (IOI07_miners)	C++17	100 / 100	498 ms	489660 KiB

miners

#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define s second
#define f first
using namespace std;

const int N = 1e5 + 5,inf = 1e18;
int dp[N][5][5][5][5],f[5],ans;

int get(char x){
	if (x == 'M') return 1;
	if (x == 'B') return 2;
	return 3;
}
int getans(int a,int b,int c){
	int mn = min({a,b,c}),mx = max({a,b,c});
	int s = a+b+c;

	a = mn,c = mx,b = s - a - c;
	if (b == 0) return 1;
	if (a == 0) {
		if (b == c) return 1;
		else return 2;
	}

	if (c == a) return 1;
	if (b == a || b == c) return 2;
	return 3;
}
signed main (){
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
	int n;
	cin>>n;

	for (int i = 0; i <= n; i++)
		for (int a=0;a<=3;a++)
			for (int b=0;b<=3;b++)
				for (int c=0;c<=3;c++)
					for (int d=0;d<=3;d++)
						dp[i][a][b][c][d] = -1;
	
	dp[0][0][0][0][0] = 0;
	for (int i = 1; i <= n; i++){
		char ch;
		cin>>ch;
		int x = get(ch);
		
		vector <pair<int,pair <pair <int,int>, pair<int,int> > > > vec;
		vec.clear();

		for (int a = 0; a <= 3; a++){
			for (int b = 0; b <= 3; b++){
				for (int c = 0; c <= 3; c++){
					for (int d = 0; d <= 3; d++){
						if (dp[i-1][a][b][c][d] < 0) continue;
						
						int val = dp[i - 1][a][b][c][d];
						int val1 = val + getans(a,b,x),val2 = val + getans(c,d,x);
						
						vec.pb({val1,{{b,x},{c,d}}});
						vec.pb({val2,{{a,b},{d,x}}});
					}
				}
			}
		}
 
		for(int j=0;j<(int)vec.size();j++){
			int val = vec[j].f;
			int a = vec[j].s.f.f,b = vec[j].s.f.s;
			int c = vec[j].s.s.f,d = vec[j].s.s.s;
			dp[i][a][b][c][d] = max(dp[i][a][b][c][d],val);
			if (i == n) ans=max(ans,dp[i][a][b][c][d]);
		}
	}
	cout<<ans;
}

• 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