oj.uz

Submission #99212

# Submission time Handle Problem Language Result Execution time Memory
99212 2019-03-01T18:06:58 Z figter001 Miners (IOI07_miners) C++17
100 / 100
 433 ms 210900 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int nax = 1e5+50;

int n,t[nax];
string s;
ll dp[nax][4][4][4][4];

ll calc(int idx,pair<int,int> a,pair<int,int> b){
	if(idx == n)
		return 0;
	ll &ret = dp[idx][a.first][a.second][b.first][b.second];
	if(ret != -1)
		return ret;
	int add = 1;
	if(a.first != 0 && a.first != t[idx])
		add++;
	if(a.second != 0 && a.second != a.first && a.second != t[idx])
		add++;
	ret = calc(idx+1,{a.second,t[idx]},b) + add;
	add = 1;
	if(b.first != 0 && b.first != t[idx])
		add++;
	if(b.second != 0 && b.second != b.first && b.second != t[idx])
		add++;
	ret = max(ret,calc(idx+1,a,{b.second,t[idx]}) + add);
	return ret;
}

int main(){
	memset(dp,-1,sizeof(dp));
	cin>>n>>s;
	for(int i=0;i<n;i++){
		if(s[i] == 'M')t[i] = 1;
		if(s[i] == 'F')t[i] = 2;
		if(s[i] == 'B')t[i] = 3;
	}
	cout << calc(0,{0,0},{0,0}) << endl;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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