Submission #868761

#	Time	Username	Problem	Language	Result	Execution time	Memory
868761		pcc	Nivelle (COCI20_nivelle)	C++14	110 / 110	93 ms	1112 KiB

nivelle

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>


string s;
int cnt[26] = {};
int n;

int check(char c = 0){
	int re = 0;
	if(c)cnt[c-'a']++;
	for(auto &i:cnt)re += (i?1:0);
	if(c)cnt[c-'a']--;
	return re;
}

pll calc(int tar){
	memset(cnt,0,sizeof(cnt));
	pll re = {1,1};
	int pt = 0;
	for(int i = 1;i<=n;i++){
		if(pt<=i){
			pt = i+1;
			memset(cnt,0,sizeof(cnt));
			cnt[s[i]-'a'] ++;
		}
		while(pt<=n&&check(s[pt])<=tar){
			cnt[s[pt]-'a']++;
			pt++;
		}
		if(re.sc-re.fs+1<pt-i)re = {i,pt-1};
		cnt[s[i]-'a']--;
	}
	return re;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>s;
	s = "#"+s;
	tlll ans = make_tuple(1,1,1);
	for(int i = 1;i<=26;i++){
		pll tmp = calc(i);
		tlll tans = make_tuple(i,tmp.fs,tmp.sc);
		if(get<0>(tans)*(get<2>(ans)-get<1>(ans)+1)<get<0>(ans)*(get<2>(tans)-get<1>(tans)+1))ans = tans;
	}
	cout<<(get<1>(ans))<<' '<<(get<2>(ans));
}

• Subtask 1: 7 / 7
• Subtask 2: 17 / 17
• Subtask 3: 13 / 13
• Subtask 4: 25 / 25
• Subtask 5: 48 / 48