oj.uz

Submission #417936

# Submission time Handle Problem Language Result Execution time Memory
417936 2021-06-04T15:40:22 Z rumen_m Miners (IOI07_miners) C++17
0 / 100
 1500 ms 97160 KB 
# 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;
    mp.erase({k,p});
    q.pop();

    int ans = mp[{k,p}];
    //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

miners.cpp: In function 'int main()':
miners.cpp:40:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     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
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct

Subtask #6
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct

Subtask #7
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 50 ms 3264 KB Output isn't correct

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 132 ms 8200 KB Output isn't correct

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 593 ms 34772 KB Output isn't correct

Subtask #10
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1367 ms 77424 KB Output isn't correct

Subtask #11
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1589 ms 97160 KB Time limit exceeded

Subtask #12
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1594 ms 95180 KB Time limit exceeded