oj.uz

Submission #417945

# Submission time Handle Problem Language Result Execution time Memory
417945 2021-06-04T16:14:49 Z rumen_m Miners (IOI07_miners) C++17
100 / 100
 1415 ms 900 KB 
# 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

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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 328 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 332 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 364 KB Output is correct

Subtask #10
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 460 KB Output is correct

Subtask #11
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1091 ms 792 KB Output is correct

Subtask #12
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1415 ms 900 KB Output is correct