제출 #844537

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
844537		vjudge1	Nivelle (COCI20_nivelle)	C++17	110 / 110	26 ms	904 KiB

nivelle

#include <iostream>
#include <algorithm>
using namespace std;

int main(){
    int n;
    string s;
    cin >> n >> s;
    int bestl = 1;
    int bestr = 1;
    int64_t bestcol = 1;
    int64_t bestlen = 1;
    int *lettercount = new int[26];
    for (int maxcolors = 1; maxcolors < 27; maxcolors++){
        for (int i = 0; i < 26; i++) lettercount[i] = 0;
        int colors = 1;
        int end = 1;
        lettercount[s[0] - 'a'] = 1;
        for (int start = 0; start < n; start++){
            if (start != 0){
                if (lettercount[s[start - 1] - 'a'] == 1) colors--;
                lettercount[s[start - 1] - 'a']--;
            }
            while (end < n && (colors < maxcolors || lettercount[s[end] - 'a'] > 0)){
                if (lettercount[s[end] - 'a'] == 0) colors++;
                lettercount[s[end] - 'a']++;
                end++;
            }
            if (colors * bestlen < (end - start) * bestcol){
                bestl = start + 1;
                bestr = end;
                bestcol = colors;
                bestlen = end - start;
            }
        }
    }
    cout << bestl << " " << bestr << endl;
}

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