Submission #519704

#	Time	Username	Problem	Language	Result	Execution time	Memory
519704		KoD	Nivelle (COCI20_nivelle)	C++17	110 / 110	34 ms	716 KiB

nivelle

#include <bits/stdc++.h>

using std::vector;
using std::array;
using std::pair;
using std::tuple;

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N;
    std::cin >> N;
    vector<int> A(N);
    for (auto& x : A) {
        char c;
        std::cin >> c;
        x = c - 'a';
    }
    int ans_x = N + 1, ans_y = 1;
    int ans_l = -1, ans_r = -1;
    for (int d = 1; d <= 26; ++d) {
        int j = 0, k = 0;
        array<int, 26> count = {};
        for (int i = 0; i < N; ++i) {
            while (j < N) {
                if (count[A[j]] == 0) {
                    k += 1;
                }
                if (k > d) {
                    k -= 1;
                    break;
                }
                count[A[j]] += 1;
                j += 1;
            }
            if (ans_x * (j - i) > d * ans_y) {
                ans_x = d, ans_y = j - i;
                ans_l = i, ans_r = j;
            }
            count[A[i]] -= 1;
            if (count[A[i]] == 0) {
                k -= 1;
            }
        }
    }
    std::cout << ans_l + 1 << ' ' << ans_r << '\n';
    return 0;
}

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