| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 250063 |
2020-07-16T19:08:06 Z |
uacoder123 |
Miners (IOI07_miners) |
C++14 |
|
700 ms |
119580 KB |
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define mp(i,a) make_pair(i,a)
#define pb(a) push_back(a)
#define bit(x,b) (x&(1LL<<b))
typedef long long int lli;
typedef pair <lli,lli> ii;
typedef pair <lli,ii> iii;
typedef vector <lli> vi;
string s;
int ans=0;
int m[100002][4][4][4][4];
string s1,s2;
void cal(int n)
{
int x=0,y=0,z=0,q=0;
if(n==s.size())
{
ans=0;
return;
}
string s3=s1,s4=s2;
int c=1,c2=1;
for(int i=int(s1.size())-1;i>=0;--i)
{
if(i==s1.size()-1)
{
if(s1[i]=='M') x=1;
if(s1[i]=='B') x=2;
if(s1[i]=='F') x=3;
}
if(i==int(s1.size())-2)
{
if(s1[i]=='M') y=1;
if(s1[i]=='B') y=2;
if(s1[i]=='F') y=3;
}
if(s1[i]!=s[n]&&c==1)
c++;
else if(c==2&&s1[i]!=s[n]&&s1[i]!=s1[i+1])
c++;
}
c2=1;
for(int i=int(s2.size())-1;i>=0;--i)
{
if(i==s2.size()-1)
{
if(s2[i]=='M') z=1;
if(s2[i]=='B') z=2;
if(s2[i]=='F') z=3;
}
if(i==int(s2.size())-2)
{
if(s2[i]=='M') q=1;
if(s2[i]=='B') q=2;
if(s2[i]=='F') q=3;
}
if(s2[i]!=s[n]&&c2==1)
c2++;
else if(c2==2&&s2[i]!=s[n]&&s2[i]!=s2[i+1])
c2++;
}
if(m[n][x][y][z][q]!=-1)
{
ans=m[n][x][y][z][q];
return;
}
if(s1.size()<2)
s1+=s[n];
else
{
s1[0]=s1[1];
s1[1]=s[n];
}
cal(n+1);
ans+=c;
s2=s4;
if(s2.size()<2)
s2+=s[n];
else
{
s2[0]=s2[1];
s2[1]=s[n];
}
s1=s3;
int ans1=ans;
cal(n+1);
ans1=max(ans1,int(c2+ans));
m[n][x][y][z][q]=ans1;
ans=ans1;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
lli test=1;
memset(m,-1,sizeof(m));
for(;test>0;--test)
{
int n;
cin>>n;
s1="",s2="";
cin>>s;
cal(0);
cout<<ans<<endl;
}
return(0);
}
Compilation message
miners.cpp: In function 'void cal(int)':
miners.cpp:24:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(n==s.size())
~^~~~~~~~~~
miners.cpp:33:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i==s1.size()-1)
~^~~~~~~~~~~~~
miners.cpp:53:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i==s2.size()-1)
~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
48 ms |
100472 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
48 ms |
100472 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
48 ms |
100472 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
48 ms |
100472 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
54 ms |
100600 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
47 ms |
100472 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
53 ms |
100728 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
61 ms |
101496 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
109 ms |
102392 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
215 ms |
105444 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
376 ms |
114852 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
700 ms |
119580 KB |
Output is correct |
