Submission #1266247

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266247		wjq	Difference (POI11_roz)	C++20	100 / 100	533 ms	13204 KiB

roz

#include <bits/stdc++.h>

using namespace std;

const int oo = (int)1e9 + 7;

int main() {
    int n; cin >> n;
    string s; cin >> s;

    vector<vector<int>> pos(26, vector<int>());
    for(int i = 0; i < n; ++i) {
        pos[s[i] - 'a'].push_back(i);
    }

    int ans = 0;
    for(int c1 = 0; c1 < 26; ++c1) {
        for(int c2 = 0; c2 < 26; ++c2) {
            if (c1 == c2) continue;

            vector<int> p(pos[c1].size() + pos[c2].size());
            merge(pos[c1].begin(), pos[c1].end(), pos[c2].begin(), pos[c2].end(), p.begin());

            // printf("c1, c2: %d %d\n", c1, c2);
            // for(int i: p) printf("%d ", i);
            // puts("");

            vector<int> a(p.size());
            for(int i = 0; i < p.size(); ++i) {
                a[i] = (s[p[i]] - 'a' == c1) ? 1 : -1;
            }

            int sumI = 0, sumJ = 0, minF = oo;
            int j = 0;

            for(int i = 0; i < p.size(); ++i) {
                sumI += a[i];
                if (a[i] == -1) {
                    while (j <= i) {
                        minF = min(minF, sumJ);
                        sumJ += a[j++];
                    }
                }
                ans = max(ans, sumI - minF);
            }
        }
    }

    cout << ans << endl;

    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