Submission #1002191

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1002191	2024-06-19T10:50:03 Z	votranngocvy	Difference (POI11_roz)	C++14	100 / 100	660 ms	19724 KB

#include<bits/stdc++.h>
    using namespace std;
    #define task "differ"
    #define ii pair<int,int>
    #define fi first
    #define se second
  //  #define int long long
    #define ld double
    #define mp make_pair
    #define lg2 20
    #define iii pair<int,ii>
    #define iiii pair<ii,ii>
    #define fii fi.fi
    #define fis fi.se
    #define sfi se.fi
    #define see se.se
    int dx[]={0LL,0LL,1,-1,1,1,-1,-1};
    int dy[]={1,-1,0LL,0LL,1,-1,1,-1};
    const int maxn=1e6+5;
    const int mod=1e9+7;
    const int inf = 0x3f3f3f3f;
    int n,s1[maxn][26],pre[maxn],tr[maxn],minn[maxn];
    int b[maxn];
    string s;
    vector<int>a[30];
    void sub1(){
        for(int i=1;i<=n;i++){
            for(int j=0;j<26;j++)
                s1[i][j]=s1[i-1][j];
            s1[i][s[i]-'a']++;
        }
        int ans=0;
        for(int i=1;i<=n;i++){
            for(int j=i+1;j<=n;j++){
                int maxx=0,minn=1e9;
                for(int k=0;k<26;k++){
                    if(s1[j][k]-s1[i-1][k]==0)break;
                    maxx=max(maxx,s1[j][k]-s1[i-1][k]);
                    minn=min(minn,s1[j][k]-s1[i-1][k]);
                }
                ans=max(ans,maxx-minn);
            }
        }
        cout<<ans;
    }
    void sub23(){
        for(int i=1;i<=n;i++){
            a[s[i]-'a'].push_back(i);
        }
        int ans=0;
        for(int i=0;i<26;i++){
            for(int j=0;j<26;j++){
                    int n=a[i].size(),n1=a[j].size();
                if(n>0&&n1>0&&i!=j){
                    int l=0,r=0,m=0;
                    while(l<n&&r<n1){
                        if(a[i][l]<a[j][r]){
                            m++;
                            b[m]=1;
                            l++;
                        }
                        else{
                            m++;
                            b[m]=-1;
                            r++;
                        }
                    }
                    while(l<n){
                        m++;
                        b[m]=1;
                        l++;
                    }
                    while(r<n1){
                        m++;
                        b[m]=-1;
                        r++;
                    }
                   /* for(int k=1;k<=m;k++)
                    cout<<b[k]<<" ";
                    cout<<'\n';*/
                    tr[0]=-1;
                    for(int k=1;k<=m;k++){
                        if(b[k]==-1)
                        tr[k]=k-1;
                        else
                        tr[k]=tr[k-1];
                    }
                    int sum=0;
                    minn[0] = 0;
                    for(int k=1;k<=m;k++){
                        sum+=b[k];
                        if(b[k]==-1)
                        ans=max(ans,sum-minn[k-1]);
                        else{
                            if(tr[k]!=-1)
                            ans=max(ans,sum-minn[tr[k]]);
                        }
                        minn[k]=min(minn[k-1],sum);
                    }
                }
            }
        }
        cout<<ans;
    }
    signed main(){
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        if(fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);}
        cin>>n>>s;
        s=' '+s;
       sub23();
    }

Compilation message

roz.cpp: In function 'int main()':
roz.cpp:109:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
roz.cpp:110:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |         freopen(task".out","w",stdout);}
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	456 KB	Output is correct
4	Correct	348 KB	Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Correct	344 KB	Output is correct
3	Correct	344 KB	Output is correct

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	512 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	7 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct

Subtask #6
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	68 ms	1108 KB	Output is correct
2	Correct	1 ms	344 KB	Output is correct
3	Correct	5 ms	604 KB	Output is correct

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	625 ms	9256 KB	Output is correct
2	Correct	472 ms	8160 KB	Output is correct
3	Correct	54 ms	7856 KB	Output is correct

Subtask #9
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	600 ms	9248 KB	Output is correct
2	Correct	59 ms	14224 KB	Output is correct
3	Correct	41 ms	9512 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	639 ms	9452 KB	Output is correct
2	Correct	39 ms	19724 KB	Output is correct
3	Correct	85 ms	8996 KB	Output is correct