Submission #291114

#	Time	Username	Problem	Language	Result	Execution time	Memory
291114		penguinhacker	Nivelle (COCI20_nivelle)	C++17	110 / 110	37 ms	768 KiB

nivelle

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

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