Submission #769698

#	Time	Username	Problem	Language	Result	Execution time	Memory
769698		Plurm	Sequence (APIO23_sequence)	C++17	28 / 100	2080 ms	29744 KiB

sequence

#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;

int sequence(int N, std::vector<int> A) {
    int mx = 0;
    for (int i = 0; i < N; i++) {
        map<int, int> cnt;
        priority_queue<int> pql;
        priority_queue<int, vector<int>, greater<int>> pqh;
        for (int j = i; j < N; j++) {
            int cur;
            cnt[A[j]]++;
            pqh.push(A[j]);
            if (pqh.size() > pql.size()) {
                int x = pqh.top();
                pqh.pop();
                pql.push(x);
            }
            while (!pqh.empty() && pql.top() > pqh.top()) {
                int x = pql.top();
                pql.pop();
                int y = pqh.top();
                pqh.pop();
                pql.push(y);
                pqh.push(x);
            }
            if (pql.size() == pqh.size() && pql.top() != pqh.top())
                cur = max(cnt[pql.top()], cnt[pqh.top()]);
            else
                cur = cnt[pql.top()];
            mx = max(mx, cur);
        }
    }
    return mx;
}

• 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