oj.uz

Submission #730846

# Submission time Handle Problem Language Result Execution time Memory
730846 2023-04-26T14:18:11 Z NintsiChkhaidze Miners (IOI07_miners) C++17
100 / 100
 498 ms 489660 KB 
#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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 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 1 ms 340 KB Output is correct

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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