In today’s lunchtime contest in the problem Chef and String I submitted a code which gave TLE on the second subcase where |S|<=10^5, the code I submitted was accepetd for |S|<=2000. The code I submitted is :
int main()
{
char s[100009];
cin>>s;
int i,j,k,l;
vector<int> x;
for(i=0;i<=4;i++)
x.push_back(0);
//2 7 4 5
int y[27];
y[2]=1;
y[7]=2;
y[4]=3;
y[5]=4;
x[0]=inf;
for(i=0;i<strlen(s);i++)
{
j=y[s[i]-'A'];
k=j-1;
if(x[k]>x[j])
x[j]++;
}
cout<<x[4]<<endl;
}
But just after I changed the use of vector x by making it an array os size 5, I got accepetd in 0.00 seconds. The change I made is shown below:
int x[5]={0};
by replacing the following code in the main program:
vector<int> x;
for(i=0;i<=4;i++)
x.push_back(0);
I don’t know why this happened. Anybody who knows the cause for this one?