oj.uz

답안 #584966

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
584966 2022-06-28T07:52:27 Z 반딧불(#8380) AAQQZ (JOI15_aaqqz) C++14
0 / 100
 1 ms 212 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll MOD1 = 1000000007;
const ll MOD2 = 1000000009;

int n, k;
int arr[3002];
int frq[3002];
int ans;

void tryMiddle1(int l1, int r1, int bonus){
    int st = -1;
    for(int j=1; l1-j>=1 && r1+j<=n; j++){
        if(arr[r1+j] != arr[l1-j]){
            st = j;
            break;
        }
    }
    if(st == -1) return;

    multiset<int> mst;
    int A = l1-st, B = r1+st;
    int prf = A+1;
    for(int j=st; l1-j>=1 && r1+j<=n; j++){
        if(st<j && arr[r1+j-1] < arr[r1+j]) break; /// ���������̾�� ��
        int key = arr[r1+j]; /// key�� ã�ƾ� ��
        if(!mst.empty() && *mst.rbegin() > key) break;
        if(!mst.empty() && *mst.rbegin() == key){
            mst.erase(mst.find(key));
            ans = max(ans, j+j+bonus);
        }
        else{
            bool good = 1;
            while(prf > 1){
                prf--;
                if(arr[prf] > key){
                    good = 0;
                    break;
                }
                mst.insert(arr[prf]);
                if(arr[prf] == key) break;
            }
            if(!good || mst.find(arr[prf]) != mst.end()) break;
            mst.erase(mst.find(arr[prf]));
            ans = max(ans, j+j+bonus);
        }
    }
}

void calc1(){
    for(int i=1; i<=n; i++){
        tryMiddle1(i, i, 1);
        if(i<n) tryMiddle1(i+1, i, 0);
    }
}

ll score[3002];
int sz;
ll A, B;
void init(){
    for(int i=1; i<=k; i++) score[i] = i;
    A=0, B=1;
    sz=0;
}
void addSet(ll i){
    A += score[i];
    B = (B * score[i]) % MOD1;
    score[i] = (score[i] + 1) * i % MOD2;
    sz++;
}

void calc2(){
    for(int i=2; i<=n; i++){
        vector<pair<ll, ll> > hashSet;
        init();
        for(int j=i; j<=n; j++){
            if(j>i && arr[j-1] < arr[j]) break; /// ���������ؾ� ��
            addSet(arr[j]);
            hashSet.push_back(make_pair(A, B));
        }
        hashSet.push_back(make_pair(1e18, 1e18));
        sort(hashSet.begin(), hashSet.end());

        init();
        int maxV = -1, maxCnt = 0;
        for(int j=i-1; j>=1; j--){
            if(maxV < arr[j]){
                for(int cnt=0; cnt<maxCnt; cnt++) addSet(maxV);
                maxV = arr[j], maxCnt = 1;
            }
            else if(maxV == arr[j]) maxCnt++;
            else addSet(arr[j]);

            pair<ll, ll> tp = make_pair(A, B);
            if(*lower_bound(hashSet.begin(), hashSet.end(), tp) == tp){
                ans = max(ans, sz*2+maxCnt);
            }
        }
    }

    for(int i=1; i<n; i++){ /// �ݴ�ε� ����
        vector<pair<ll, ll> > hashSet;
        init();
        for(int j=i; j>=1; j--){
            if(j<i && arr[j] < arr[j+1]) break; /// ���������ؾ� ��
            addSet(arr[j]);
            hashSet.push_back(make_pair(A, B));
        }
        hashSet.push_back(make_pair(1e18, 1e18));
        sort(hashSet.begin(), hashSet.end());

        init();
        int minV = INT_MAX, minCnt = 0;
        for(int j=i+1; j<=n; j++){
            if(minV > arr[j]){
                for(int cnt=0; cnt<minCnt; cnt++) addSet(minV);
                minV = arr[j], minCnt = 1;
            }
            else if(minV == arr[j]) minCnt++;
            else addSet(arr[j]);

            pair<ll, ll> tp = make_pair(A, B);
            if(*lower_bound(hashSet.begin(), hashSet.end(), tp) == tp){
                ans = max(ans, sz*2+minCnt);
            }
        }
    }
}

int main(){
    scanf("%d %d", &n, &k);
    for(int i=1; i<=n; i++) scanf("%d", &arr[i]), frq[arr[i]]++;
    ans = *max_element(frq+1, frq+k+1);

    for(int i=1; i<=n; i++){
        for(int j=1; i-j>=1 && i+j<=n; j++){
            if(arr[i+j] != arr[i-j]) break;
            ans = max(ans, j+j+1);
        }
    }
    for(int i=1; i<n; i++){
        for(int j=0; i-j>=1 && i+j+1<=n; j++){
            if(arr[i-j] != arr[i+j+1]) break;
            ans = max(ans, j+j+2);
        }
    }

    /// 1. ���� ������ ȸ�� ������ ��ġ�µ�, ȸ���� �߾��� ��ġ�� �ʴ� ���
    /// 2. ȸ���� �߾��� ���� ������ ���Ե� ���
//    calc1();
    calc2();

    printf("%d", ans);
}

Compilation message

aaqqz.cpp: In function 'void tryMiddle1(int, int, int)':
aaqqz.cpp:25:20: warning: unused variable 'B' [-Wunused-variable]
   25 |     int A = l1-st, B = r1+st;
      |                    ^
aaqqz.cpp: In function 'int main()':
aaqqz.cpp:134:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  134 |     scanf("%d %d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~
aaqqz.cpp:135:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  135 |     for(int i=1; i<=n; i++) scanf("%d", &arr[i]), frq[arr[i]]++;
      |                             ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 90.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -