# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
447050 |
2021-07-24T10:25:00 Z |
grt |
Nivelle (COCI20_nivelle) |
C++17 |
|
43 ms |
716 KB |
#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second
#define _ ios_base::sync_with_stdio(0); cin.tie(0);
//mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
using namespace std;
using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;
const int INF = 1e9;
int n;
string s;
int cnt[26];
pi ans = {INF, 1};
pi res;
int main() {_
cin >> n >> s;
for(int d = 1; d <= 26; ++d) {
for(int i = 0; i < 26; ++i) cnt[i] = 0;
int j = -1;
int mx_len = 0;
pi best = {-1,-1};
int dif = 0;
for(int i = 0; i < n; ++i) {
while(j + 1 < n && dif + (cnt[s[j + 1] - 'a'] == 0) <= d) {
cnt[s[j + 1] - 'a']++;
dif += (cnt[s[j + 1] - 'a'] == 1);
j++;
}
mx_len = max(mx_len, j - i + 1);
if(mx_len == j - i + 1) {
best = {i, j};
}
cnt[s[i] - 'a']--;
dif -= (cnt[s[i] - 'a'] == 0);
}
//~ cout << d << " " << mx_len << "\n";
if((ll)ans.ST * mx_len > (ll)ans.ND * d) {
ans = {d, mx_len};
res = best;
}
}
cout << res.ST + 1 << " " << res.ND + 1;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
312 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
216 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
604 KB |
Output is correct |
2 |
Correct |
29 ms |
588 KB |
Output is correct |
3 |
Correct |
26 ms |
588 KB |
Output is correct |
4 |
Correct |
26 ms |
588 KB |
Output is correct |
5 |
Correct |
28 ms |
716 KB |
Output is correct |
6 |
Correct |
29 ms |
620 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
576 KB |
Output is correct |
2 |
Correct |
28 ms |
588 KB |
Output is correct |
3 |
Correct |
28 ms |
588 KB |
Output is correct |
4 |
Correct |
30 ms |
608 KB |
Output is correct |
5 |
Correct |
28 ms |
588 KB |
Output is correct |
6 |
Correct |
29 ms |
588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
39 ms |
604 KB |
Output is correct |
2 |
Correct |
39 ms |
588 KB |
Output is correct |
3 |
Correct |
40 ms |
588 KB |
Output is correct |
4 |
Correct |
39 ms |
604 KB |
Output is correct |
5 |
Correct |
41 ms |
604 KB |
Output is correct |
6 |
Correct |
43 ms |
604 KB |
Output is correct |