Submission #487603

#	Time	Username	Problem	Language	Result	Execution time	Memory
487603		KazamaHoang	Nivelle (COCI20_nivelle)	C++14	110 / 110	83 ms	632 KiB

nivelle

#include <bits/stdc++.h>

using namespace std;

int n;
string s;
double res = 1e9;
int l = 0, r = 0;
int last[26];

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> s;
    s = " " + s;
    for (int i = n; i >= 1; -- i) {
        last[s[i]-'a'] = i;
        vector<int> min_pos = {n+1};
        for (int j = 0; j < 26; ++ j) 
            if (last[j])
                min_pos.push_back(last[j]);
        sort(min_pos.begin(), min_pos.end());
        for (int j = 0; j + 1 < (int)min_pos.size(); ++ j) {
            double cur = (double)(j + 1) / (min_pos[j+1] - i);
            if (res > cur) {
                res = cur;
                l = i;
                r = min_pos[j+1] - 1;
            } 
        }
    }
    cout << l << " " << r;
    return 0;
}

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