Submission #986808

#	Time	Username	Problem	Language	Result	Execution time	Memory
986808		PaDi	Difference (POI11_roz)	C++14	100 / 100	213 ms	18036 KiB

roz

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int maxn=1000010;
int n,ans;
int pre[maxn],s[maxn],f[maxn][2],head[30];
char str[maxn];
void calc(int cn)
{
    int i;
    for(i=1;i<=n;i++)    s[i]=s[i-1]+(str[i]=='a'+cn);
    if(!s[n])   return ;
    f[0][0]=0,f[0][1]=-1<<30;
    for(i=1;i<=n;i++)
    {
        if(str[i]=='a'+cn)  continue;
        f[i][0]=max(f[pre[i]][0]+1-s[i]+s[pre[i]],1);
        f[i][1]=(s[i]>s[pre[i]])?max(f[pre[i]][0]+1-s[i]+s[pre[i]],0):(f[pre[i]][1]+1);
        ans=max(ans,f[i][1]);
        if(s[n]-s[i])   ans=max(ans,f[i][0]-1);
    }
}
int main()
{
    scanf("%d%s",&n,str+1);
    int i;
    for(i=1;i<=n;i++)    pre[i]=head[str[i]-'a'],head[str[i]-'a']=i;
    for(i=0;i<26;i++)    calc(i);
    printf("%d",ans);
    return 0;
}
 

Compilation message (stderr)

roz.cpp: In function 'int main()':
roz.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |     scanf("%d%s",&n,str+1);
      |     ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10