Submission #256660

#	Time	Username	Problem	Language	Result	Execution time	Memory
256660		MrRobot_28	Nivelle (COCI20_nivelle)	C++17	110 / 110	114 ms	768 KiB

nivelle

#include<bits/stdc++.h>
 
using namespace std;
#define int long long
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n;
	cin >> n;
	string s;
	cin >> s;
	int cnt = n;
	int l = 0, r = n - 1;
	vector <int> end(26, -1);
	for(int i = 0; i < n; i++)
	{
		vector <int> mass;
		end[s[i] - 'a'] = i;
		for(int j = 0; j < 26; j++){
			if(end[j] != -1)
			{
				mass.push_back(end[j]);
			}
		}
		sort(mass.begin(), mass.end());
		int c = 0;
		for(int j = mass.size() - 1; j >= 0; j--)
		{
			if(mass[j] < i)
			{
				if(cnt * (i - mass[j]) > c * (r - l + 1))
				{
					l = mass[j] + 1;
					r = i;
					cnt = c;
				}
			}
			c++;
		}
		if(cnt * (i + 1) > c * (r - l + 1))
		{
			l = 0;
			r = i;
			cnt = c;
		}
	}
	cout << l + 1 << " " << r + 1;
	return 0;
}

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