oj.uz

Submission #201011

# Submission time Handle Problem Language Result Execution time Memory
201011 2020-02-09T05:34:17 Z dolphingarlic Nivelle (COCI20_nivelle) C++14
110 / 110
 45 ms 760 KB 
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

int active[26];
pair<int, int> mx[27];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    string s;
    cin >> n >> s;
    FOR(i, 1, 27) {
        mx[i] = {1, 0};
        int l = 0, colours = 0;
        fill(active, active + 26, 0);
        FOR(r, 0, n) {
            active[s[r] - 'a']++;
            if (active[s[r] - 'a'] == 1) colours++;
            while (colours > i) {
                active[s[l] - 'a']--;
                if (active[s[l] - 'a'] == 0) colours--;
                l++;
            }
            if (r - l > mx[i].second - mx[i].first) mx[i] = {l + 1, r + 1};
        }
    }

    long double mn = 1e18;
    pair<int, int> ans = {0, -1};
    FOR(i, 1, 27) {
        if ((long double)i / (mx[i].second - mx[i].first + 1) <= mn) {
            ans = mx[i];
            mn = (long double)i / (mx[i].second - mx[i].first + 1);
        }
    }
    cout << ans.first << ' ' << ans.second;
    return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 508 KB Output is correct
2 Correct 5 ms 380 KB Output is correct
3 Correct 5 ms 380 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 6 ms 504 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 6 ms 408 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 6 ms 376 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 632 KB Output is correct
2 Correct 18 ms 632 KB Output is correct
3 Correct 17 ms 632 KB Output is correct
4 Correct 18 ms 632 KB Output is correct
5 Correct 18 ms 632 KB Output is correct
6 Correct 18 ms 632 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 632 KB Output is correct
2 Correct 21 ms 632 KB Output is correct
3 Correct 20 ms 632 KB Output is correct
4 Correct 21 ms 632 KB Output is correct
5 Correct 20 ms 632 KB Output is correct
6 Correct 22 ms 632 KB Output is correct

Subtask #5
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 632 KB Output is correct
2 Correct 42 ms 632 KB Output is correct
3 Correct 42 ms 632 KB Output is correct
4 Correct 41 ms 632 KB Output is correct
5 Correct 43 ms 632 KB Output is correct
6 Correct 45 ms 760 KB Output is correct