oj.uz

Submission #235587

# Submission time Handle Problem Language Result Execution time Memory
235587 2020-05-28T16:49:20 Z Pbezz Miners (IOI07_miners) C++14
100 / 100
 195 ms 200952 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 10000000
#define MAXN 100005
typedef pair<int, int> pii; 

ll int DP[MAXN][4][4][4][4];
bitset<4>bi;

int main(){

	ll int n,i,k,a,b,c,d,cur,ans=0;
	cin>>n;
	string s; 
	cin>>s;

	memset(DP,(ll int)-1,sizeof(DP));

	DP[0][0][0][0][0]=0;

	for(i=1;i<=n;i++){

	if(s[i-1]=='M'){
	k=1;
	}else if(s[i-1]=='F'){
	k=2;
	}else{
	k=3;
	}

	for(a=0;a<=3;a++){
	for(b=0;b<=3;b++){
	for(c=0;c<=3;c++){
	for(d=0;d<=3;d++){
	cur = DP[i-1][a][b][c][d];

	if(cur==-1)continue;

	if( (b==0&&a!=0) || (d==0&&c!=0) )continue;

	//vai para left
	bi.reset();

	bi[a]=1; bi[b]=1; bi[k]=1; bi[0]=0;

	DP[i][b][k][c][d] = max(DP[i][b][k][c][d],cur+(int)bi.count());

	//vai para right

	bi.reset();

	bi[c]=1; bi[d]=1; bi[k]=1; bi[0]=0;

	DP[i][a][b][d][k] = max(DP[i][a][b][d][k],cur+(int)bi.count());

	}	}	}	}

}

	for(a=0;a<=3;a++){
	for(b=0;b<=3;b++){
	for(c=0;c<=3;c++){
	for(d=0;d<=3;d++){

	ans=max(ans,DP[n][a][b][c][d]);
	//cout<<a<<" "<<b<<" "<<c<<" "<<d<<"  "<<DP[n-1][a][b][c][d]<<"  "<<DP[n][a][b][c][d]<<"\n";

}	}	}	}

cout<<ans<<endl;

  
return 0; 
}

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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