Submission #844412

#	Time	Username	Problem	Language	Result	Execution time	Memory
844412		vjudge1	Nivelle (COCI20_nivelle)	C++17	62 / 110	1031 ms	21592 KiB

nivelle

#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve(){
	int n;cin >> n;
	string inp;cin >> inp;
	int mx = 0;
	for(auto itr : inp)mx = max(mx , (long long)itr - 'a');
	if(mx <= 7){
		string str = "abcdefg";
		int k = 7;

		int arr[n],cur[n];
		for(int i = 0;i<n;i++){
			char ch = inp[i];
			arr[i] = ch - 'a';
		}
		memset(cur , 0 , sizeof(cur));

		int pay = 1 , payda = 0 , l = 1 , r = 1;

		for(int bit = 0;bit < (1 << k);bit++){
			for(int j = 0;j<n;j++){
				cur[j] = (bit >> arr[j]) & 1;
			}
			int mx = 0 , sayac = 0 , templ = 1 , tempr = 1;
			for(int i = 0;i<=n;i++){
				if(i != n and cur[i] == 1){
					sayac++;
				}
				else{
					if(mx < sayac){
						mx = sayac;
						templ = i - sayac + 1;
						tempr = i;
					}
					sayac = 0;
				}
			}
			if(pay * mx > ((int)__builtin_popcount(bit)) * payda){
				pay = ((int)__builtin_popcount(bit));
				payda = mx;
				l = templ;
				r = tempr;
			}
		}
		cout << l << " " << r << endl;
	}
	else{
		int cnt[n+1][26],arr[n+1];
		memset(cnt , 0 , sizeof(cnt));
		for(int i = 1;i<=n;i++){
			char ch = inp[i-1];
			arr[i] = ch - 'a';
			cnt[i][arr[i]]++;
			for(int j = 0;j<26;j++){
				cnt[i][j] += cnt[i-1][j];
			}
		}
		int pay = 2*n , payda = 1 , l = 1 , r = 1;
		for(int i = 1;i<=n;i++){
			for(int j = i;j<=n;j++){
				int dif = 0 , len = j - i + 1;
				for(int k = 0;k<26;k++)dif += (cnt[j][k] - cnt[i-1][k]) > 0;
				if(pay * len > dif * payda){
					pay = dif;
					payda = len;
					l = i;
					r = j;
				}
			}
		}
		cout << l << " " << r << endl;
	}
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int testcase = 1;//cin >> testcase;
	while(testcase--)solve();
}

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