oj.uz

Submission #151325

# Submission time Handle Problem Language Result Execution time Memory
151325 2019-09-02T13:09:28 Z GioChkhaidze Miners (IOI07_miners) C++14
100 / 100
 150 ms 1072 KB 
#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

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

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 424 KB Output is correct

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 1072 KB Output is correct