제출 #1306590

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1306590		nguyenkhangninh99	Nivelle (COCI20_nivelle)	C++20	110 / 110	50 ms	24808 KiB

nivelle

#include<bits/stdc++.h>
using namespace std;

#define int long long
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int n; cin >> n;
  	string s; cin >> s;
  	vector<vector<int>> p(n + 1, vector<int>(27, n));
  	for(int i = n - 1; i >= 0; i--){
  		p[i] = p[i + 1];
  		p[i][s[i] - 'a'] = i;
  	}
  	int L = -1, R, LEN;
  	for(int i = 0; i < n; i++){
  		sort(p[i].begin(), p[i].end());
  		for(int j = 0; p[i][j] < n; j++){
  			if(L == -1 || (j + 1) * (R - L + 1) < LEN * (p[i][j + 1] - i)){
                  //(p[i][j + 1] - 1 - i + 1) / (j + 1) VS (R - L + 1) / LEN
  				L = i;
  				R = p[i][j + 1] - 1;
  				LEN = j + 1;
  			}
  		}
  	}
      
  	cout << L + 1 << " " << R + 1;
}

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