Submission #844478

#	Time	Username	Problem	Language	Result	Execution time	Memory
844478		vjudge1	Nivelle (COCI20_nivelle)	C++17	24 / 110	1055 ms	11092 KiB

nivelle

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

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

int arr[N][26];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    string str;

    cin >> n >> str;

    str = "#" + str;

    for(int i = 1; i <= n; i++)
    {
        arr[i][str[i] - 'a']++;
    }

    for(int i = 1; i <= n; i++)
    {
        for(int j = 0; j < 26; j++)
        {
            arr[i][j] += arr[i - 1][j];
        }
    }

    int left = 1, right = 1;
    long double ans = 1;

    for(int i = 1; i <= n; i++)
    {
        for(int j = i + 1; j <= n; j++)
        {
            int cnt = 0;

            for(int k = 0; k < 26; k++)
            {
                if(arr[j][k] - arr[i - 1][k])
                {
                    cnt++;
                }
            }
            long double l = j - i + 1;

            if((long double)cnt / l < ans)
            {
                ans = (long double)cnt / l;
                left = i, right = j;
            }
        }
    }

    cout << left << " " << right << '\n';
}

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