Submission #1103916

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103916		ShadowShark	Difference (POI11_roz)	C++17	100 / 100	66 ms	2540 KiB

roz

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

int sum[26][26], mn[26][26], cont[26][26];
/// define: array[first_char][second_char]: if first_char = 1 and second_char = -1;
/// mn: largest containing the second_char
/// cont: save the sum of the previous position before the second_char appear

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n;
    cin >> n;

    string s;
    cin >> s;

    for (int i = 0; i < 26; i++)
        for (int j = 0; j < 26; j++)
            mn[i][j] = 1e9;

    int ans = 0;
    for (auto ch: s) {
        int x = ch - 'a';
        for (int y = 0; y < 26; y++) {
            if (x == y) continue;
            sum[x][y]++;
            ans = max(ans, sum[x][y] - mn[x][y]);

            sum[y][x]--;
            mn[y][x] = min(mn[y][x], cont[y][x]);
            cont[y][x] = sum[y][x];
            ans = max(ans, sum[y][x] - mn[y][x]);
        }
    }

    cout << ans;
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10