Submission #979357

#	Time	Username	Problem	Language	Result	Execution time	Memory
979357		MilosMilutinovic	Difference (POI11_roz)	C++14	100 / 100	958 ms	14568 KiB

roz

#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 / 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