Submission #120662

#	Time	Username	Problem	Language	Result	Execution time	Memory
120662		baluteshih	Miners (IOI07_miners)	C++14	100 / 100	49 ms	640 KiB

miners

#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 / 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