Submission #417939

#	Time	Username	Problem	Language	Result	Execution time	Memory
417939		rumen_m	Miners (IOI07_miners)	C++17	84 / 100	1578 ms	460 KiB

miners

# include <bits/stdc++.h>
using namespace std;
map <pair <int,string > ,int> mp;
priority_queue <pair <int, string> > q;
int query(char a, char b, char c)
{
    char 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 main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n,i,j;
cin>>n;
string s;
cin>>s;
q.push({-0,"0000"});
int ANS = 0;
while(!q.empty())
{
    int k = -q.top().first;
    string p = q.top().second;

    q.pop();

    int ans = mp[{k,p}];
    auto it = mp.find({k,p}); mp.erase(it);
    //cout<<k<<" "<<p<<" "<<ans<<endl;
    char ch = s[k];if(k>=s.size())break;
    int ans1 = ans+query(p[0],p[1],ch);
    ANS = max(ANS,ans1);
    string l = "";
    l+=p[1];
    l+=ch;
    l+=p[2];
    l+=p[3];
   // cout<<l<<endl;
    if(mp.count({k+1,l})==0)
        {
            mp[{k+1,l}] = ans1;
            q.push({-k-1,l});
        }
        else
            mp[{k+1,l}] = max(mp[{k+1,l}],ans1);
          ans1 = ans+query(p[2],p[3],ch);
          ANS = max(ANS,ans1);
      l = "";
    l+=p[0];
    l+=p[1];
    l+=p[3];
    l+=ch;
        //  l="";
    //l += p[0]+p[1]+p[3]+ch;
    if(mp.count({k+1,l})==0)
        {
            mp[{k+1,l}] = ans1;
              q.push({-k-1,l});
        }
        else
            mp[{k+1,l}] = max(mp[{k+1,l}],ans1);
    }
cout<<ANS<<endl;
return 0;
}

Compilation message (stderr)

miners.cpp: In function 'int main()':
miners.cpp:41:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     char ch = s[k];if(k>=s.size())break;
      |                       ~^~~~~~~~~~
miners.cpp:25:7: warning: unused variable 'i' [-Wunused-variable]
   25 | int n,i,j;
      |       ^
miners.cpp:25:9: warning: unused variable 'j' [-Wunused-variable]
   25 | int n,i,j;
      |         ^

• 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