oj.uz

Submission #986808

# Submission time Handle Problem Language Result Execution time Memory
986808 2024-05-21T09:12:38 Z PaDi Difference (POI11_roz) C++14
100 / 100
 213 ms 18036 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 756 KB Output is correct
4 Correct 0 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 600 KB Output is correct
2 Correct 1 ms 348 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 2396 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 4 ms 820 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 18036 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 125 ms 14692 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 18008 KB Output is correct
2 Correct 156 ms 14424 KB Output is correct
3 Correct 99 ms 15532 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 18028 KB Output is correct
2 Correct 90 ms 18012 KB Output is correct
3 Correct 105 ms 17888 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 18032 KB Output is correct
2 Correct 84 ms 18000 KB Output is correct
3 Correct 122 ms 18012 KB Output is correct