oj.uz

Submission #95164

# Submission time Handle Problem Language Result Execution time Memory
95164 2019-01-27T19:05:10 Z FedericoS Miners (IOI07_miners) C++14
100 / 100
 160 ms 73508 KB 
#include <iostream>
using namespace std;
typedef pair<int,int> pii;

int N;
char c;
int DP[4][4][4][4][100005];
int T[100005];

int C(pii a, int b){
	int A[]={0,0,0,0};
	A[a.first]=1;
	A[a.second]=1;
	A[b]=1;
	return A[1]+A[2]+A[3];
}

int F(pii a, pii b, int k){
	if(k==N) return 0;

	if(!DP[a.first][a.second][b.first][b.second][k])
		DP[a.first][a.second][b.first][b.second][k]=
			max(
				F({a.second,T[k]},b,k+1)+C(a,T[k]),
				F(a,{b.second,T[k]},k+1)+C(b,T[k])
			);

	return DP[a.first][a.second][b.first][b.second][k];
}


int main(){
	cin>>N;
	for(int i=0;i<N;i++){
		cin>>c;
		if(c=='M')
			T[i]=1;
		else if(c=='F')
			T[i]=2;
		else
			T[i]=3;
	}

	cout<<F({0,0},{0,0},0);

}

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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