Submission #151325

#	Time	Username	Problem	Language	Result	Execution time	Memory
151325		GioChkhaidze	Miners (IOI07_miners)	C++14	100 / 100	150 ms	1072 KiB

miners

#include <bits/stdc++.h>
using namespace std;
int n,a[100005],D_[4][4][4][4],D[4][4][4][4],f1[5],f2[5],ANS;
string s;
main ()
{
	cin>>n>>s;
	
	for (int i=0; i<n; i++) {
		if (s[i]=='M') a[i+1]=1;
		if (s[i]=='B') a[i+1]=2;
		if (s[i]=='F') a[i+1]=3;
	}
	
	for (int i=0; i<=n; i++) 
		for (int i1=0; i1<=3; i1++)
			for (int i2=0; i2<=3; i2++) 
				for (int j1=0; j1<=3; j1++)
					for (int j2=0; j2<=3; j2++) 
						D_[i1][i2][j1][j2]=-1,D[i1][i2][j1][j2]=-1,
	
	D_[0][0][0][0]=0;
	
	for (int i=1; i<=n; i++) {
		for (int i1=0; i1<=3; i1++)
			for (int i2=0; i2<=3; i2++) {
				if (!i1 && i2) continue;
	
				for (int j1=0; j1<=3; j1++)
					for (int j2=0; j2<=3; j2++) {
						if (!j1 && j2) continue;
						
						if (D_[i1][i2][j1][j2]==-1) continue;
						
						f1[1]=f1[2]=f1[3]=0;
						f2[1]=f2[2]=f2[3]=0;
						f1[a[i]]=1,f1[i1]=1,f1[i2]=1;
						f2[a[i]]=1,f2[j1]=1,f2[j2]=1;
						int A1=f1[1]+f1[2]+f1[3];
						int A2=f2[1]+f2[2]+f2[3];
						
						D[a[i]][i1][j1][j2]=max(D_[i1][i2][j1][j2]+A1,D[a[i]][i1][j1][j2]);
						D[i1][i2][a[i]][j1]=max(D_[i1][i2][j1][j2]+A2,D[i1][i2][a[i]][j1]);
					}
			}
			
		for (int i1=0; i1<=3; i1++)
			for (int i2=0; i2<=3; i2++) 
				for (int j1=0; j1<=3; j1++)
					for (int j2=0; j2<=3; j2++) 
						D_[i1][i2][j1][j2]=D[i1][i2][j1][j2],D[i1][i2][j1][j2]=-1;		
	}
	
	for (int i1=0; i1<=3; i1++)
		for (int i2=0; i2<=3; i2++) 
			for (int j1=0; j1<=3; j1++)
				for (int j2=0; j2<=3; j2++) 
					ANS=max(ANS,D_[i1][i2][j1][j2]);
				
	cout<<ANS<<endl;
}

Compilation message (stderr)

miners.cpp:5:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main ()
       ^

• Subtask 1: 9 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 7 / 7
• Subtask 7: 8 / 8
• Subtask 8: 8 / 8
• Subtask 9: 8 / 8
• Subtask 10: 8 / 8
• Subtask 11: 8 / 8
• Subtask 12: 8 / 8