Submission #476481

#	Time	Username	Problem	Language	Result	Execution time	Memory
476481		starplat	Nivelle (COCI20_nivelle)	C++14	110 / 110	45 ms	640 KiB

nivelle

#include <bits/stdc++.h>
using namespace std;
int n,ct,l,r,ac[150],j;
string s;
double best;
int main()
{
	cin>>n>>s;
	s=' '+s;
	for (int k=1;k<=26;k++){
		memset(ac,0,sizeof(ac));
		ct=0,j=0;
		for (int i=1;i<=n;i++){
			while (j<n&&ct<=k){
				j++;
				if (ac[s[j]-'a']==0){
					if (ct+1>k) {
						j--;
						break;
					}
					ct++;
				} 
				ac[s[j]-'a']++;
			}
			//if (ct==2)	cout<<i<<" "<<j<<" "<<ct<<"\n";
			if (l==0||best>k/(double)(j-i+1)){
				best=k/(double)(j-i+1);
				l=i,r=j;
			}
			ac[s[i]-'a']--;
			if (ac[s[i]-'a']==0) ct--;
		}
	}
	cout<<l<<" "<<r<<"\n";
}

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