# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
417937 |
2021-06-04T15:40:54 Z |
rumen_m |
Miners (IOI07_miners) |
C++17 |
|
1500 ms |
488 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;
q.pop();
int ans = mp[{k,p}]; mp.erase({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;
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
35 ms |
296 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
79 ms |
300 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
403 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
867 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1588 ms |
488 KB |
Time limit exceeded |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1592 ms |
460 KB |
Time limit exceeded |