oj.uz

Submission #979357

# Submission time Handle Problem Language Result Execution time Memory
979357 2024-05-10T17:03:36 Z MilosMilutinovic Difference (POI11_roz) C++14
100 / 100
 958 ms 14568 KB 
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  string s;
  cin >> s;
  const int A = 26;
  vector<vector<int>> pos(A);
  for (int i = 0; i < n; i++) {
    pos[(int) (s[i] - 'a')].push_back(i);
  }
  int ans = 0;
  for (int i = 0; i < A; i++) {
    if (pos[i].empty()) {
      continue;
    }
    for (int j = 0; j < A; j++) {
      if (pos[j].empty()) {
        continue;
      }
      vector<int> a;
      int pi = 0, pj = 0;
      while (pi < (int) pos[i].size() || pj < (int) pos[j].size()) {
        if (pi == (int) pos[i].size()) {
          a.push_back(-1);
          pj += 1;
        } else if (pj == (int) pos[j].size()) {
          a.push_back(1);
          pi += 1;
        } else if (pos[i][pi] < pos[j][pj]) {
          a.push_back(1);
          pi += 1;
        } else {
          a.push_back(-1);
          pj += 1;
        }
      }
      int sz = (int) a.size();
      vector<int> pref(sz + 1);
      for (int p = 0; p < sz; p++) {
        pref[p + 1] = pref[p] + a[p];
      }
      int mn = (int) 1e9;
      vector<int> lst(2, -1);
      int ptr = 0;
      for (int p = 1; p <= sz; p++) {
        lst[a[p - 1] == 1 ? 1 : 0] = p;
        while (ptr < min(lst[0], lst[1])) {
          mn = min(mn, pref[ptr]);
          ptr += 1;
        }
        ans = max(ans, pref[p] - mn);
      }
    }
  }
  cout << ans << '\n';
  return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 1 ms 368 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 388 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 460 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 1116 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 6 ms 604 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 938 ms 9632 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 470 ms 7768 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 958 ms 9296 KB Output is correct
2 Correct 612 ms 7676 KB Output is correct
3 Correct 179 ms 7212 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 942 ms 9528 KB Output is correct
2 Correct 95 ms 13060 KB Output is correct
3 Correct 137 ms 8460 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 816 ms 9140 KB Output is correct
2 Correct 58 ms 14568 KB Output is correct
3 Correct 218 ms 8152 KB Output is correct