Submission #549423

#	Time	Username	Problem	Language	Result	Execution time	Memory
549423		someone	Nivelle (COCI20_nivelle)	C++14	110 / 110	29 ms	1424 KiB

nivelle

#include <bits/stdc++.h>
#define int long long
using namespace std;
 
const int N = 1e5 + 42, INF = 1e18 + 42;

string str;
int n, a = INF, b = 1, l = -1, r = -1, val[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n >> str;
    for(int i = 0; i < n; i++)
        val[i] = str[i] - 'a';
    for(int i = 1; i <= 26; i++) {
        int fin = 0, occ[26] = {0}, t = 0;
        for(int deb = 0; deb < n; deb++) {
            while(fin < n && ((occ[val[fin]] && t == i) || t < i)) {
                if(!occ[val[fin]])
                    t++;
                occ[val[fin]]++;
                fin++;
            }
            if(a * (fin - deb) > b * i) {
                l = deb, r = fin;
                a = i, b = (fin - deb);
            }
            occ[val[deb]]--;
            if(!occ[val[deb]])
                t--;
        }
    }
    cout << l+1 << ' ' << r;
}

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