fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int N, C;
  5. int A[3005], freq[3005], ans;
  6. bool isPal[3005][3005];
  7.  
  8. void build_palindrome_dp() {
  9.     for (int len = 1; len <= N; len++) {
  10.         for (int l = 1; l + len - 1 <= N; l++) {
  11.             int r = l + len - 1;
  12.             if (l == r) isPal[l][r] = true;
  13.             else if (A[l] == A[r]) {
  14.                 if (len == 2) isPal[l][r] = true;
  15.                 else isPal[l][r] = isPal[l+1][r-1];
  16.             } else isPal[l][r] = false;
  17.             if (isPal[l][r]) ans = max(ans, len);
  18.         }
  19.     }
  20. }
  21.  
  22. // 정렬 구간을 선택하고 회문 확장 시도
  23. void try_extend(int centerL, int centerR) {
  24.     // 기존 회문 중심에서 바깥으로 확장 가능
  25.     while (centerL > 1 && centerR < N && A[centerL-1] == A[centerR+1]) {
  26.         centerL--; centerR++;
  27.     }
  28.  
  29.     // 왼쪽 확장 후보 (비증가 구간)
  30.     vector<int> leftVals;
  31.     int prevVal = -1;
  32.     for (int i = centerL-1; i >= 1; i--) {
  33.         if (prevVal == -1 || prevVal <= A[i]) {
  34.             leftVals.push_back(A[i]);
  35.             prevVal = A[i];
  36.         } else break;
  37.     }
  38.     if (leftVals.empty()) return;
  39.  
  40.     // 이진 탐색: 왼쪽에서 m개를 정렬에 사용
  41.     int lo = 0, hi = (int)leftVals.size() - 1;
  42.     while (lo <= hi) {
  43.         int mid = (lo + hi) / 2;
  44.  
  45.         // 사용 가능한 값 카운트
  46.         vector<int> cnt(C+1, 0);
  47.         for (int i = 0; i <= mid; i++) cnt[leftVals[i]]++;
  48.  
  49.         int matched = 0;
  50.         bool ok = true, strictRight = true;
  51.         for (int i = centerR+1; i <= N && matched <= mid; i++) {
  52.             if (cnt[A[i]]) {
  53.                 cnt[A[i]]--;
  54.                 matched++;
  55.             } else {
  56.                 strictRight = false;
  57.                 if (A[i] < leftVals[mid]) { ok = false; break; }
  58.             }
  59.         }
  60.         ok &= (matched > mid);
  61.  
  62.         if (ok) {
  63.             int L = centerL - mid - 1;
  64.             int R = centerR + mid + 1;
  65.             if (strictRight) {
  66.                 while (L > 1 && R < N && A[L-1] == A[R+1]) {
  67.                     L--; R++;
  68.                 }
  69.             }
  70.             ans = max(ans, R - L + 1);
  71.             lo = mid + 1;
  72.         } else hi = mid - 1;
  73.     }
  74. }
  75.  
  76. void solve_direction() {
  77.     build_palindrome_dp();
  78.     for (int center = 1; center <= N; center++) {
  79.         // 홀수 길이 중심
  80.         int l = center, r = center;
  81.         while (l > 1 && r < N && isPal[l-1][r+1]) { l--; r++; }
  82.         try_extend(l, r);
  83.  
  84.         // 짝수 길이 중심
  85.         l = center; r = center - 1;
  86.         while (l > 1 && r < N && isPal[l-1][r+1]) { l--; r++; }
  87.         try_extend(l, r);
  88.     }
  89. }
  90.  
  91. int main() {
  92.     ios::sync_with_stdio(false);
  93.     cin.tie(nullptr);
  94.  
  95.     cin >> N >> C;
  96.     for (int i = 1; i <= N; i++) {
  97.         cin >> A[i];
  98.         freq[A[i]]++;
  99.     }
  100.     for (int i = 1; i <= C; i++) ans = max(ans, freq[i]);
  101.  
  102.     solve_direction();
  103.     reverse(A+1, A+N+1);
  104.     for (int i = 1; i <= N; i++) A[i] = C - A[i] + 1;
  105.     solve_direction();
  106.  
  107.     cout << ans << "\n";
  108.     return 0;
  109. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
4 3
1
2
3
2
stdout
copy 
3
https://ideone.com/txiYZ1
language:
C++ (gcc 8.3)
created:
22 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!