Submission #1306590

#TimeUsernameProblemLanguageResultExecution timeMemory
1306590nguyenkhangninh99Nivelle (COCI20_nivelle)C++20
110 / 110
50 ms24808 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...