oj.uz

Submission #618808

# Submission time Handle Problem Language Result Execution time Memory
618808 2022-08-02T07:35:00 Z 1ne Miners (IOI07_miners) C++14
84 / 100
 1063 ms 524288 KB 
#include<bits/stdc++.h>
using namespace std;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n;cin>>n;
	string s;cin>>s;
	auto getid = [&](char u){
		if (u == 'M')return 0;
		else if (u == 'B')return 1;
		return 2;
	};
	vector<int>a(2,-1),b(2,-1);
	vector<map<vector<int>,map<vector<int>,int>>>dp(n),came(n);
	function<int(int,vector<int>&,vector<int>&)>solve = [&](int u,vector<int>&arr,vector<int>&brr){
		if (u == n)return 0;
		if (came[u][arr][brr])return dp[u][arr][brr];
		came[u][arr][brr] = true;
		int temp = getid(s[u]);
		vector<int>crr(2);
		crr[0] = arr[1];
		crr[1] = temp;
		vector<int>drr(2);
		drr[0] = brr[1];
		drr[1] = temp;
		int cnts = 0,cnts2 = 0;
		if (arr[0] != -1)cnts++;
		if (arr[1] != -1 && arr[1]!=arr[0])cnts++;
		if (temp!=arr[0] && temp!=arr[1])cnts++;
		if (brr[0] != -1)cnts2++;
		if (brr[1] != -1 && brr[1]!=brr[0])cnts2++;
		if (temp!=brr[0] && temp!=brr[1])cnts2++;
		long long ans = max(solve(u + 1,crr,brr) + cnts , solve(u + 1,arr,drr) + cnts2);
		return dp[u][arr][brr] = ans; 
	};
	cout<<solve(0,a,b)<<'\n';
	return 0;
}

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 340 KB Output is correct

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 885 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #12
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 1025 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -