31E - TV Game - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;

char s[40];
unsigned long long pw[20],dp[40][20];

int main()
{
int i,j,k,n;
scanf("%d%s",&n,s+1);
pw[0]=1;
for(i=1;i<=n;i++) pw[i]=pw[i-1]*10;
for(i=n*2;i>=1;i--)
{
for(j=0;j<=n&&j<=n*2-i+1;j++)
{
k=n*2-i+1-j;
if(j) dp[i][j]=max(dp[i][j],dp[i+1][j-1]+pw[j]*(s[i]-'0'));
if(k) dp[i][j]=max(dp[i][j],dp[i+1][j]+pw[k]*(s[i]-'0'));
}
}
for(i=1,j=n;i<=n*2;i++)
{
if(j&&dp[i][j]==dp[i+1][j-1]+pw[j]*(s[i]-'0')) printf("H"),j--;
else printf("M");
}
return 0;
}