Submission #250273

#	Time	Username	Problem	Language	Result	Execution time	Memory
250273		dvdg6566	Nivelle (COCI20_nivelle)	C++14	24 / 110	1097 ms	1024 KiB

nivelle

#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';
}

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