oj.uz

Submission #120662

# Submission time Handle Problem Language Result Execution time Memory
120662 2019-06-25T07:29:14 Z baluteshih Miners (IOI07_miners) C++14
100 / 100
 49 ms 640 KB 
#include <bits/stdc++.h>
#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pb push_back
#define ET cout << "\n"
#define MEM(i,j) memset(i,j,sizeof i)
#define F first
#define S second
#define MP make_pair
#define ALL(v) v.begin(),v.end()
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

int dp[2][14][14];
const int INF=2e9;
string s;
 
int main()
{jizz
	int n,nw=1,pst=0,ans=0;
	cin >> n >> s;
	for(int j=1;j<14;++j)
		for(int k=1;k<14;++k)
			dp[0][j][k]=-INF;
	dp[0][1][1]=0;
	for(int i=n-1;i>=0;--i,swap(nw,pst))
	{
		for(int j=1;j<14;++j)
			for(int k=1;k<14;++k)
				dp[nw][j][k]=-INF;
		if(s[i]=='M')
			for(int j=1;j<14;++j)
			{
				dp[nw][2][j]=max(dp[nw][2][j],dp[pst][1][j]+1);
				dp[nw][5][j]=max({dp[nw][5][j],dp[pst][2][j]+1,dp[pst][5][j]+1,dp[pst][6][j]+1,dp[pst][7][j]+1});
				dp[nw][6][j]=max({dp[nw][6][j],dp[pst][3][j]+2,dp[pst][8][j]+3,dp[pst][9][j]+2,dp[pst][10][j]+3});
				dp[nw][7][j]=max({dp[nw][7][j],dp[pst][4][j]+2,dp[pst][11][j]+3,dp[pst][12][j]+2,dp[pst][13][j]+3});
				dp[nw][j][2]=max(dp[nw][j][2],dp[pst][j][1]+1);
				dp[nw][j][5]=max({dp[nw][j][5],dp[pst][j][2]+1,dp[pst][j][5]+1,dp[pst][j][6]+1,dp[pst][j][7]+1});
				dp[nw][j][6]=max({dp[nw][j][6],dp[pst][j][3]+2,dp[pst][j][8]+3,dp[pst][j][9]+2,dp[pst][j][10]+3});
				dp[nw][j][7]=max({dp[nw][j][7],dp[pst][j][4]+2,dp[pst][j][11]+3,dp[pst][j][12]+2,dp[pst][j][13]+3});
			}
		else if(s[i]=='F')
			for(int j=1;j<14;++j)
			{
				dp[nw][3][j]=max(dp[nw][3][j],dp[pst][1][j]+1);
				dp[nw][8][j]=max({dp[nw][8][j],dp[pst][3][j]+1,dp[pst][8][j]+1,dp[pst][9][j]+1,dp[pst][10][j]+1});
				dp[nw][9][j]=max({dp[nw][9][j],dp[pst][2][j]+2,dp[pst][5][j]+3,dp[pst][6][j]+2,dp[pst][7][j]+3});
				dp[nw][10][j]=max({dp[nw][10][j],dp[pst][4][j]+2,dp[pst][11][j]+3,dp[pst][12][j]+3,dp[pst][13][j]+2});
				dp[nw][j][3]=max(dp[nw][j][3],dp[pst][j][1]+1);
				dp[nw][j][8]=max({dp[nw][j][8],dp[pst][j][3]+1,dp[pst][j][8]+1,dp[pst][j][9]+1,dp[pst][j][10]+1});
				dp[nw][j][9]=max({dp[nw][j][9],dp[pst][j][2]+2,dp[pst][j][5]+3,dp[pst][j][6]+2,dp[pst][j][7]+3});
				dp[nw][j][10]=max({dp[nw][j][10],dp[pst][j][4]+2,dp[pst][j][11]+3,dp[pst][j][12]+3,dp[pst][j][13]+2});
			}
		else
			for(int j=1;j<14;++j)
			{
				dp[nw][4][j]=max(dp[nw][4][j],dp[pst][1][j]+1);
				dp[nw][11][j]=max({dp[nw][11][j],dp[pst][4][j]+1,dp[pst][11][j]+1,dp[pst][12][j]+1,dp[pst][13][j]+1});
				dp[nw][12][j]=max({dp[nw][12][j],dp[pst][2][j]+2,dp[pst][5][j]+3,dp[pst][6][j]+3,dp[pst][7][j]+2});
				dp[nw][13][j]=max({dp[nw][13][j],dp[pst][3][j]+2,dp[pst][8][j]+3,dp[pst][9][j]+3,dp[pst][10][j]+2});
				dp[nw][j][4]=max(dp[nw][j][4],dp[pst][j][1]+1);
				dp[nw][j][11]=max({dp[nw][j][11],dp[pst][j][4]+1,dp[pst][j][11]+1,dp[pst][j][12]+1,dp[pst][j][13]+1});
				dp[nw][j][12]=max({dp[nw][j][12],dp[pst][j][2]+2,dp[pst][j][5]+3,dp[pst][j][6]+3,dp[pst][j][7]+2});
				dp[nw][j][13]=max({dp[nw][j][13],dp[pst][j][3]+2,dp[pst][j][8]+3,dp[pst][j][9]+3,dp[pst][j][10]+2});
			}
	}
	for(int i=1;i<14;++i)
		for(int j=1;j<14;++j)
			ans=max(ans,dp[pst][i][j]);
	cout << ans << "\n";
}

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 384 KB Output is correct

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 404 KB Output is correct

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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