Submission #250060

#	Time	Username	Problem	Language	Result	Execution time	Memory
250060		uacoder123	Miners (IOI07_miners)	C++14	84 / 100	1600 ms	215288 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;
map<pair<int,pair<string,string>>,int> m;
string s1,s2;
void cal(int n)
{
   if(n==s.size())
   {
       ans=0;
       return;
   }
   if(m.find(mp(n,mp(s1,s2)))!=m.end())
   {
      ans=m[mp(n,mp(s1,s2))];
      return;
   }
   string s3=s1,s4=s2;
   int c=1;
   for(int i=int(s1.size())-1;i>=0;--i)
   {
    if(s1[i]!=s[n]&&c==1)
      c++;
    else if(c==2&&s1[i]!=s[n]&&s1[i]!=s1[i+1])
      c++;
   }
   if(s1.size()<2)
      s1+=s[n];
   else
   {
      s1[0]=s1[1];
      s1[1]=s[n];
   }
   cal(n+1);
   ans+=c;
   s2=s4;
   c=1;
   for(int i=int(s2.size())-1;i>=0;--i)
   {
    if(s2[i]!=s[n]&&c==1)
      c++;
    else if(c==2&&s2[i]!=s[n]&&s2[i]!=s2[i+1])
      c++;
   }
   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(c+ans));
   m[mp(n,mp(s3,s4))]=ans1;
   ans=ans1;
}
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  lli test=1;
  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:23:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(n==s.size())
       ~^~~~~~~~~~

• 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: 0 / 8
• Subtask 12: 0 / 8