제출 #1260650

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1260650		duongquanghai08	새로운 문제 (POI11_roz)	C++20	90 / 100	682 ms	13240 KiB

roz

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 6;
const int W = 26;
int n;
string s;
vector<int> pos[W];
int ans[N];
void Solve() {
    cin >> n >> s;
    for (int i = 0; i < n; i++) pos[s[i] - 'a'].push_back(i);
    int maxDiff = 0;
    for (int x = 0; x < W; x++) {
        if (pos[x].empty()) continue;
        for (int y = 0; y < W; y++) {
            if (x == y || pos[y].empty()) continue;
            int j = 0;
            vector<int> a;
            a.push_back(0);
            for(int i : pos[x]) {
                while(j < pos[y].size() && pos[y][j] < i) a.push_back(-1), j++;
                a.push_back(1);
            }
            int last = 0, minPre = n + 1;
            vector<int> pre(a.size(), 0);
            for(int i = 1; i < a.size(); i++) {
                pre[i] = pre[i - 1] + a[i];
                if(i > 1 &&  a[i] != a[i - 1]) {
                    for(int j = last; j < i - 1; j++) minPre = min(minPre, pre[j]);
                    last = i - 1;
                }
                maxDiff = max(maxDiff, pre[i] - minPre);
            }
        }
    }
    cout << maxDiff;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    //freopen("CHENHLECH.INP", "r", stdin);
    //freopen("CHENHLECH.OUT", "w", stdout);
    Solve();

    return 0;
}

• Subtask 1: 0 / 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