Submission #250273

#TimeUsernameProblemLanguageResultExecution timeMemory
250273dvdg6566Nivelle (COCI20_nivelle)C++14
24 / 110
1097 ms1024 KiB
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pi;
typedef vector<pi> vpi;
typedef long double ld;
#define pb emplace_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define ALL(x) x.begin(), x.end() 
#define SZ(x) (ll)x.size()
#define f first
#define s second
const ll MAXN=200001;
const ll MAXK=1000001;
const ll INF = 1e9;
const ll MOD = 1e9+7;

string S;
int A[MAXN];
int p[MAXN];
int N;

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>N>>S;
	for(int i=0;i<26;++i){
		int x=-1;
		for(int t=0;t<N;++t)if(S[t]-'a'==i){
			p[t]=x;
			x=t;
		}
	}
	ld optcst=-1;
	pi ans=mp(-1,-1);
	for(int st=0;st<N;++st){
		int l=0;
		int u=0;
		for(int en=st;en<N;++en){
			++l;
			if(p[en]<st)++u;
			ld c=(ld)l/(ld)u;
			if(c>optcst){
				ans=mp(st,en);
				optcst=c;
			}
		}
	}
	cout<<ans.f+1<<' '<<ans.s+1<<'\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...