제출 #198251

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
198251		alrad	Nivelle (COCI20_nivelle)	C++17	110 / 110	44 ms	632 KiB

nivelle

#include <bits/stdc++.h>

using namespace std;

typedef long double ld;

int main() {
   ios_base :: sync_with_stdio(0);
   cin.tie(0) , cout.tie(0);
   int n;
   cin >> n;
   vector<char> s(n);
   for (int i = 0; i < n; i++) {
      cin >> s[i];
   }
   long double ans = 2.0;
   int L = 0 , R = 0;
   for (int cnt = 1; cnt <= 26; cnt++) {
      vector<int> tot(26 , 0);
      int r = 0 , x = 0;
      for (int i = 0; i < n; i++) {
         while (r < n && x <= cnt) {
            if (!tot[int(s[r] - 'a')]) {
               if (x + 1 > cnt) {
                  break;
               }
               x++;
            }
            tot[int(s[r] - 'a')]++;
            r++;
         }
         if (ld(cnt) / ld(r - i) < ans) {
            ans = ld(cnt) / ld(r - i);
            L = i;
            R = r - 1;
         }
         if (tot[int(s[i] - 'a')] == 1) {
            x--;
         }
         tot[int(s[i] - 'a')]--;
      }
   }
   cout << L + 1 << " " << R + 1 << '\n';
   return 0;
}

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