Submission #959205

#	Time	Username	Problem	Language	Result	Execution time	Memory
959205		kilkuwu	Sequence (APIO23_sequence)	C++17	28 / 100	2083 ms	54476 KiB

sequence

#include "sequence.h"

#include <bits/stdc++.h>

int sequence(int N, std::vector<int> A) {
  int ans = 1;
  for (int i = 0; i < N; i++) {
    std::map<int, int> mp;
    std::multiset<int> s;
    mp[A[i]]++;
    s.insert(A[i]);
    auto it = s.begin();
    int idx = 0;
    for (int j = i + 1; j < N; j++) {
      s.insert(A[j]);
      mp[A[j]]++;
      
      if (A[j] < *it) {
        idx++;
      }

      int med_idx = s.size() / 2;
      if (idx < med_idx) {
        it++;
        idx++;
      }
      if (idx > med_idx) {
        it--;
        idx--;
      }

      ans = std::max(ans, mp[*it]);

      if (s.size() % 2 == 0) {
        ans = std::max(ans, mp[*std::prev(it)]);
      }
    }
  }
  return ans;
}

#ifdef LOCAL

#include <cassert>
#include <cstdio>

#include <vector>

int main() {
  int N;
  assert(1 == scanf("%d", &N));

  std::vector<int> A(N);
  for (int i = 0; i < N; ++i) {
    assert(1 == scanf("%d", &A[i]));
  }

  int result = sequence(N, A);
  printf("%d\n", result);
  return 0;
}
#endif

• Subtask 1: 11 / 11
• Subtask 2: 17 / 17
• Subtask 3: 0 / 7
• Subtask 4: 0 / 12
• Subtask 5: 0 / 13
• Subtask 6: 0 / 22
• Subtask 7: 0 / 18