Submission #250063

#	Time	Username	Problem	Language	Result	Execution time	Memory
250063		uacoder123	Miners (IOI07_miners)	C++14	100 / 100	700 ms	119580 KiB

miners

#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define mp(i,a) make_pair(i,a)
#define pb(a) push_back(a)
#define bit(x,b) (x&(1LL<<b))

typedef long long int lli;
typedef pair <lli,lli> ii;
typedef pair <lli,ii> iii;
typedef vector <lli> vi;
string s;
int ans=0;
int m[100002][4][4][4][4];
string s1,s2;
void cal(int n)
{
  int x=0,y=0,z=0,q=0;
   if(n==s.size())
   {
       ans=0;
       return;
   }
   string s3=s1,s4=s2;
   int c=1,c2=1;
   for(int i=int(s1.size())-1;i>=0;--i)
   {
    if(i==s1.size()-1)
    {
      if(s1[i]=='M') x=1;
      if(s1[i]=='B') x=2;
      if(s1[i]=='F') x=3;
    }
    if(i==int(s1.size())-2)
    {
      if(s1[i]=='M') y=1;
      if(s1[i]=='B') y=2;
      if(s1[i]=='F') y=3;
    }
    if(s1[i]!=s[n]&&c==1)
      c++;
    else if(c==2&&s1[i]!=s[n]&&s1[i]!=s1[i+1])
      c++;
   }
   c2=1;
   for(int i=int(s2.size())-1;i>=0;--i)
   {
    if(i==s2.size()-1)
    {
      if(s2[i]=='M') z=1;
      if(s2[i]=='B') z=2;
      if(s2[i]=='F') z=3;
    }
    if(i==int(s2.size())-2)
    {
      if(s2[i]=='M') q=1;
      if(s2[i]=='B') q=2;
      if(s2[i]=='F') q=3;
    }
    if(s2[i]!=s[n]&&c2==1)
      c2++;
    else if(c2==2&&s2[i]!=s[n]&&s2[i]!=s2[i+1])
      c2++;
   }
   if(m[n][x][y][z][q]!=-1)
   {
      ans=m[n][x][y][z][q];
      return;
   }
   if(s1.size()<2)
      s1+=s[n];
   else
   {
      s1[0]=s1[1];
      s1[1]=s[n];
   }
   cal(n+1);
   ans+=c;
   s2=s4;
   if(s2.size()<2)
      s2+=s[n];
   else
   {
      s2[0]=s2[1];
      s2[1]=s[n];
   }
   s1=s3;
   int ans1=ans;
   cal(n+1);
   ans1=max(ans1,int(c2+ans));
   m[n][x][y][z][q]=ans1;
   ans=ans1;
}
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  lli test=1;
  memset(m,-1,sizeof(m));
  for(;test>0;--test)
  {
   int n;
   cin>>n;
   s1="",s2="";
   cin>>s;
   cal(0);
   cout<<ans<<endl;
  }
  return(0);
}

Compilation message (stderr)

miners.cpp: In function 'void cal(int)':
miners.cpp:24:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(n==s.size())
       ~^~~~~~~~~~
miners.cpp:33:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(i==s1.size()-1)
        ~^~~~~~~~~~~~~
miners.cpp:53:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(i==s2.size()-1)
        ~^~~~~~~~~~~~~

• 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