제출 #814610

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
814610		Hanksburger	서열 (APIO23_sequence)	C++17	28 / 100	226 ms	31728 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]));
            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+3)/2)
                    r=mid;
                else
                    l=mid+1;
            }
            ans=max(ans, freq[j][l]-(i==0?0:freq[i-1][l]));
        }
    }
    return ans;
}

• 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