oj.uz

답안 #585003

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
585003 2022-06-28T08:27:54 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 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 || arr[pnt-1] <= arr[j])){
                pnt--;
                if(arr[pnt] == maxVal) maxCnt++;
                else mst.insert(arr[pnt]);
            }
            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 || arr[pnt+1] >= arr[j])){
                pnt++;
                if(arr[pnt] == minVal) minCnt++;
                else mst.insert(arr[pnt]);
            }
            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:113:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |     scanf("%d %d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~
aaqqz.cpp:114:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |     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 1 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 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -