제출 #1017461

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1017461		vjudge1	Nivelle (COCI20_nivelle)	C++17	110 / 110	55 ms	12508 KiB

nivelle

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

#define ll long long
int const N=2e5+5;
int const mod=1e9+7;

int nxt[N][30];

int main(){
	int n;
	cin>>n;
	string s;
	cin>>s;
	for(int i=0;i<30;i++)
		nxt[n][i]=n;
	for(int i=n-1;i>=0;i--){
		for(int j=0;j<30;j++)
			nxt[i][j]=nxt[i+1][j];
		nxt[i][s[i]-'a']=i;
	}
	int l=0,r=0;
	int len=1,d=1;
	for(int i=0;i<n;i++){

		sort(nxt[i],nxt[i]+26);
		for(int c=0;c<=26;c++){
			int ln=nxt[i][c]-i;
			if(c*len<d*ln){
				// cout<<i<<' '<<c<<endl;
				l=i;
				r=nxt[i][c]-1;
				d=c;
				len=ln;
			}
		}
	}
	cout<<l+1<<' '<<r+1<<endl;
	return 0;
}

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