Submission #417945

#	Time	Username	Problem	Language	Result	Execution time	Memory
417945		rumen_m	Miners (IOI07_miners)	C++17	100 / 100	1415 ms	900 KiB

miners

# include <bits/stdc++.h>
using namespace std;
map <pair <int,string > ,int> mp;
priority_queue <pair <int, string> > q;
int query(int a, int b, int c)
{
    int v[3];
    v[0] = a;
    v[1] = b;
    v[2] = c;
    int ans = 0;
    sort(v,v+3);
    for(int i=0;i<3;i++)
    {
        if(i==0||v[i]!=v[i-1])
            if(v[i]!=0)ans++;
    }
  // cout<<a<<" "<<b<<" "<<c<<" -> "<<ans<<endl;
    return ans;
}int ANS = 0;
int chmax(int a, int b)
{
    if(a>b){if(ANS<a)ANS=a;return a;}
    if(ANS<b)ANS=b;
    return b;
}
int s[100005];
int dp[2][18][18];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n,i,j;
cin>>n;
string w;

cin>>w;

for(i=0;i<w.size();i++)
{
    if(w[i]=='F')s[i] = 1;
    if(w[i]=='M')s[i] = 2;
    if(w[i]=='B')s[i] = 3;
}
//dp[0][s[0]][0] = 1;
bool fl = 1;

for(int z=n-1;z>=0;z--)
{
    int k = s[z];
    for(i=0;i<16;i++)
    {
     for(j=0;j<16;j++)
     {
         int t1 = i/4;
         int t2 = i%4;
         int p1 = j/4;
         int p2 = j%4;

         int q1 = t2*4+k;
      //   cout<<dp[!fl][i][j]<<endl;
         dp[fl][i][j] = chmax(dp[fl][i][j],dp[!fl][q1][j]+query(t1,t2,k));
         //cout<<z<<" : "<<t2<<" "<<k<<" - "<<p1<<" "<<p2<<" :: "<< dp[fl][q1][j]<<endl;
         int q2 = p2*4+k;
         dp[fl][i][j] = chmax(dp[fl][i][j],dp[!fl][i][q2]+query(p1,p2,k));
          //cout<<z<<" : "<<t1<<" "<<t2<<" - "<<p2<<" "<<k<<" :: "<< dp[fl][i][q2]<<endl;
     }
    }
    fl=!fl;
}
cout<<dp[!fl][0][0]<<endl;
return 0;
}

Compilation message (stderr)

miners.cpp: In function 'int main()':
miners.cpp:39:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 | for(i=0;i<w.size();i++)
      |         ~^~~~~~~~~

• 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