oj.uz

Submission #113418

# Submission time Handle Problem Language Result Execution time Memory
113418 2019-05-25T13:03:33 Z TadijaSebez Miners (IOI07_miners) C++11
100 / 100
 67 ms 768 KB 
#include <bits/stdc++.h>
using namespace std;
const int N=100050;
const int inf=1e9+7;
int a[N];
char s[N];
int dp[2][4][4][4][4];
void ckmx(int &a, int b){ a=max(a,b);}
int pre[4][4][4];
int Get(int a, int b, int c)
{
	return pre[a][b][c];
}
int Get1(int a, int b, int c)
{
	set<int> st;
	if(a) st.insert(a);
	if(b) st.insert(b);
	if(c) st.insert(c);
	return st.size();
}
void Clear(int t)
{
	for(int i=0;i<4;i++)
		for(int j=0;j<4;j++)
			for(int k=0;k<4;k++)
				for(int l=0;l<4;l++)
					dp[t][i][j][k][l]=-inf;
}
void Build()
{
	for(int i=0;i<4;i++)
		for(int j=0;j<4;j++)
			for(int k=0;k<4;k++)
				pre[i][j][k]=Get1(i,j,k);
}
int main()
{
	Build();
	int n,i;
	scanf("%i",&n);
	scanf("%s",s+1);
	for(int i=1;i<=n;i++)
	{
		if(s[i]=='M') a[i]=1;
		if(s[i]=='B') a[i]=2;
		if(s[i]=='F') a[i]=3;
	}
	int c=0,p=1;
	Clear(p);
	dp[p][0][0][0][0]=0;
	for(int t=1;t<=n;t++)
	{
		int tmp=a[t];
		Clear(c);
		for(int i=0;i<4;i++)
			for(int j=0;j<4;j++)
				for(int k=0;k<4;k++)
					for(int l=0;l<4;l++)
					{
						ckmx(dp[c][i][j][l][tmp],dp[p][i][j][k][l]+Get(k,l,tmp));
						ckmx(dp[c][j][tmp][k][l],dp[p][i][j][k][l]+Get(i,j,tmp));
					}
		swap(c,p);
	}
	int ans=-inf;
	for(int i=0;i<4;i++)
		for(int j=0;j<4;j++)
			for(int k=0;k<4;k++)
				for(int l=0;l<4;l++)
					ans=max(ans,dp[p][i][j][k][l]);
	printf("%i\n",ans);
	return 0;
}

Compilation message

miners.cpp: In function 'int main()':
miners.cpp:40:8: warning: unused variable 'i' [-Wunused-variable]
  int n,i;
        ^
miners.cpp:41:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i",&n);
  ~~~~~^~~~~~~~~
miners.cpp:42:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s",s+1);
  ~~~~~^~~~~~~~~~

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 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 2 ms 384 KB Output is correct

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 384 KB Output is correct

Subtask #11
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 640 KB Output is correct

Subtask #12
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 768 KB Output is correct