Submission #814368

#	Time	Username	Problem	Language	Result	Execution time	Memory
814368		Hanksburger	Sequence (APIO23_sequence)	C++17	11 / 100	153 ms	31700 KiB

sequence

#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;
int freq[2005][2005], freqsum[2005][2005];
int sequence(int n, vector<int> a)
{

    for (int i=0; i<n; i++)
        freq[i][a[i]]++;
    for (int i=1; i<n; i++)
        for (int j=1; j<=n; j++)
            freq[i][j]+=freq[i-1][j];
    for (int i=0; i<n; i++)
        for (int j=1; j<=n; j++)
            freqsum[i][j]=freqsum[i][j-1]+freq[i][j];
    int ans=0;
    for (int i=0; i<n; i++)
    {
        for (int j=i; j<n; j++)
        {
            int l=1, r=n;
            while (l<r)
            {
                int mid=(l+r)/2;
                if (freqsum[j][mid]-(i==0?0:freqsum[i-1][mid])>=(j-i+2)/2)
                    r=mid;
                else
                    l=mid+1;
            }
            ans=max(ans, freq[j][l]-(i==0?0:freq[i-1][l]));
            if (freqsum[j][l]-(i==0?0:freqsum[i-1][l])<(j-i+3)/2)
                ans=max(ans, freq[j][l+1]-(i==0?0:freq[i-1][l+1]));
        }
    }
    return ans;
}

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