제출 #291114

#제출 시각아이디문제언어결과실행 시간메모리
291114penguinhackerNivelle (COCI20_nivelle)C++17
110 / 110
37 ms768 KiB
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

int n, cnt[26];
string s;

void add(int i, int& colors) {if (++cnt[s[i]-'a']==1) ++colors;}
void sub(int i, int& colors) {if (--cnt[s[i]-'a']==0) --colors;}

ar<int, 3> ans={10000000, -1, -1};
void updAns(int k, int l, int r) {
	//answer is ans[0]/(ans[2]-ans[1]+1)
	//current is k/(r-l+1)
	//want to update if (k)/(r-l+1)<ans[0]/(ans[2]-ans[1]+1) --> k*(ans[2]-ans[1]+1)<ans[0]*(r-l+1)
	if (k*(ans[2]-ans[1]+1)<ans[0]*(r-l+1)) ans={k, l, r};
}

void solve(int k) {
	memset(cnt, 0, sizeof(cnt));
	int colors=0;
	for (int l=0, r=0; r<n; ++r) {
		add(r, colors);
		while(colors>k) sub(l++, colors);
		updAns(k, l, r);
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> s;
	for (int i=1; i<=26; ++i) solve(i);
	//cout << ans[0] << " " << ans[1]+1 << " " << ans[2]+1 << "\n";
	cout << ans[1]+1 << " " << ans[2]+1 << "\n";
	return 0;
}
#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...