Submission #1233130

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233130		erering	Difference (POI11_roz)	C++20	30 / 100	104 ms	1508 KiB

roz

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define endl '\n'
//#define int long long
const int N=1e6+5,inf=2e8,MOD=1e9+7;
int best[26][26],pref[26],last[26],cnt[26][26];
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //a[i]-a[j]-b[i]+b[j]
    //a[i]-b[i]-a[j]+b[j]
    for(int i=0;i<26;i++){
        last[i]=-1;
        for(int j=0;j<26;j++)best[i][j]=-inf;
    }
    int n; cin>>n;
    string s; cin>>s;
    int sol=0;
    for(int i=0;i<n;i++){
        int id=s[i]-'a';
        pref[id]++;
        for(int j=0;j<26;j++){
            if(j==id || last[j]==-1)continue;
            int ans=pref[id]-pref[j];
            ans+=best[id][j];
          //  if(ans==4)cout<<pref[id]-pref[j]<<' '<<best[id][j]<<' '<<i<<endl;
            sol=max(sol,ans);
            if(last[id]<last[j]){
            //    if(i==2)cout<<j<<' '<<i<<' '<<-mn[j]+pref[s[i]-'a']<<endl;
                best[j][id]=max(best[j][id],-(pref[j]-cnt[id][j])+pref[id]-1);
               // if(j==0 && id==1)cout<<i<<' '<<(cnt[id][j])<<' '<<pref[id]<<' '<<-(pref[j]-cnt[id][j])+pref[id]-1<<endl;
            }
            cnt[id][j]=0;
            cnt[j][id]++;
        }
        last[id]=i;
    }
    cout<<sol;
}

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