oj.uz

답안 #584996

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
584996 2022-06-28T08:21:52 Z 반딧불(#8380) AAQQZ (JOI15_aaqqz) C++14
0 / 100
 0 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 calc1(){
    for(int i=2; i<=n; i++){
        int pnt = i;
        int maxVal = -1, maxCnt = 0;
        multiset<int> mst;
        while(pnt > 1){
            pnt--;
            if(arr[i] < arr[pnt]){
                maxVal = arr[pnt];
                maxCnt = 1;
                break;
            }
            mst.insert(arr[pnt]);
        }
        if(maxVal==-1) continue;

        for(int j=i; j<=n; j++){
            if(!mst.empty() && *mst.rbegin() > arr[j]) break;
            if(!mst.empty() && *mst.rbegin() == arr[j]){
                ans = max(ans, 2*(j-i+1)+maxCnt);
                mst.erase(mst.find(arr[j]));
                continue;
            }
            bool good = 1;
            while(pnt > 1){
                pnt--;
                if(arr[pnt] > arr[j]){
                    if(arr[pnt] == maxVal){
                        maxCnt++;
                        continue;
                    }
                    good = 0;
                    break;
                }
                mst.insert(arr[pnt]);
                if(arr[pnt] == arr[j]) break;
            }
            while(pnt > 1 && arr[pnt-1] == maxVal){
                pnt++;
                maxCnt++;
            }
            if(!good || (mst.empty() || *mst.rbegin() < arr[j])) break;
            ans = max(ans, 2*(j-i+1)+maxCnt);
            mst.erase(mst.find(arr[j]));
        }
    }
}

void calc2(){
    for(int i=1; i<n; i++){
        int pnt = i;
        int minVal = 1e9, minCnt = 0;
        multiset<int> mst;
        while(pnt < n){
            pnt++;
            if(arr[i] > arr[pnt]){
                minVal = arr[pnt];
                minCnt = 1;
                break;
            }
            mst.insert(arr[pnt]);
        }
        if(minVal==1e9) continue;

        for(int j=i; j>=1; j--){
            if(!mst.empty() && *mst.begin() < arr[j]) break;
            if(!mst.empty() && *mst.begin() == arr[j]){
                ans = max(ans, 2*(i-j+1)+minCnt);
                mst.erase(mst.find(arr[j]));
                continue;
            }
            bool good = 1;
            while(pnt < n){
                pnt++;
                if(arr[pnt] < arr[j]){
                    if(arr[pnt] == minVal){
                        minCnt++;
                        continue;
                    }
                    good = 0;
                    break;
                }
                mst.insert(arr[pnt]);
                if(arr[pnt] == arr[j]) break;
            }
            while(pnt < n && arr[pnt+1] == minVal){
                pnt++;
                minCnt++;
            }
            if(!good || (mst.empty() || *mst.begin() > arr[j])) break;
            ans = max(ans, 2*(i-j+1)+minCnt);
            mst.erase(mst.find(arr[j]));
        }
    }
}

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 'int main()':
aaqqz.cpp:111:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |     scanf("%d %d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~
aaqqz.cpp:112:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |     for(int i=1; i<=n; i++) scanf("%d", &arr[i]), frq[arr[i]]++;
      |                             ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

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