oj.uz

Submission #730855

# Submission time Handle Problem Language Result Execution time Memory
730855 2023-04-26T14:29:32 Z NintsiChkhaidze Miners (IOI07_miners) C++17
100 / 100
 238 ms 100508 KB 
#include <bits/stdc++.h>
#define pb push_back
#define s second
#define f first
using namespace std;

const int N = 1e5 + 5;
int dp[N][4][4][4][4],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;

		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;
						vec.pb({dp[i - 1][a][b][c][d] + getans(a,b,x),{{b,x},{c,d}}});
						vec.pb({dp[i - 1][a][b][c][d] + getans(c,d,x),{{a,b},{d,x}}});
					}
 
		for(int j=0;j<(int)vec.size();j++){
			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],vec[j].f);
			if (i == n) ans=max(ans,dp[i][a][b][c][d]);
		}
	}
	cout<<ans;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1236 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5332 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 10348 KB Output is correct

Subtask #10
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 25364 KB Output is correct

Subtask #11
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 75464 KB Output is correct

Subtask #12
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 100508 KB Output is correct