Submission #235585

#	Time	Username	Problem	Language	Result	Execution time	Memory
235585		Pbezz	Miners (IOI07_miners)	C++14	56 / 100	197 ms	200952 KiB

miners

#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]=='M'){
	k=1;
	}else if(s[i]=='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: 0 / 9
• Subtask 2: 0 / 9
• Subtask 3: 0 / 9
• Subtask 4: 9 / 9
• Subtask 5: 0 / 9
• Subtask 6: 7 / 7
• Subtask 7: 0 / 8
• Subtask 8: 8 / 8
• Subtask 9: 8 / 8
• Subtask 10: 8 / 8
• Subtask 11: 8 / 8
• Subtask 12: 8 / 8