fork download 
  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 updateLongestPalindrome() {
  9.     for (int i = N; i >= 1; --i) {
  10.         for (int j = i; j <= N; ++j) {
  11.             if (i == j) isPal[i][j] = true;
  12.             else if (i+1 == j) isPal[i][j] = (A[i] == A[j]);
  13.             else isPal[i][j] = (A[i] == A[j] && isPal[i+1][j-1]);
  14.             if (isPal[i][j]) ans = max(ans, j - i + 1);
  15.         }
  16.     }
  17. }
  18.  
  19. // 중심 (l,r)에서 시작해 정렬된 구간을 하나 삽입했을 때 가능한 최대 회문 길이
  20. void tryExpand(int l, int r) {
  21.     // 왼쪽 확장 가능한 비내림 구간 찾기
  22.     vector<int> leftSeq;
  23.     int prev = -1;
  24.     for (int i = l-1; i >= 1; --i) {
  25.         if (prev == -1 || prev <= A[i]) {
  26.             leftSeq.push_back(A[i]);
  27.             prev = A[i];
  28.         } else break;
  29.     }
  30.     if (leftSeq.empty()) return;
  31.     reverse(leftSeq.begin(), leftSeq.end());
  32.  
  33.     int Lsize = (int)leftSeq.size();
  34.     // 이분 탐색: 왼쪽에서 몇 개를 정렬로 가져갈지
  35.     int lo = 0, hi = Lsize-1;
  36.     while (lo <= hi) {
  37.         int mid = (lo + hi) / 2;
  38.         vector<int> cnt(C+1, 0);
  39.         for (int i = 0; i <= mid; ++i) cnt[leftSeq[i]]++;
  40.         int matched = 0;
  41.         bool can = true, pureSym = true;
  42.  
  43.         for (int i = r+1; i <= N && matched <= mid; ++i) {
  44.             if (cnt[A[i]] > 0) {
  45.                 cnt[A[i]]--;
  46.                 matched++;
  47.             } else {
  48.                 pureSym = false;
  49.                 if (A[i] < leftSeq[mid]) can = false;
  50.             }
  51.         }
  52.         can &= (matched > mid);
  53.  
  54.         if (can) {
  55.             int Lpos = l - mid - 1, Rpos = r + mid + 1;
  56.             if (pureSym) while (Lpos > 1 && Rpos < N && A[Lpos-1] == A[Rpos+1]) {
  57.                 Lpos--; Rpos++;
  58.             }
  59.             ans = max(ans, Rpos - Lpos + 1);
  60.             lo = mid + 1;
  61.         } else hi = mid - 1;
  62.     }
  63. }
  64.  
  65. void solveDirection() {
  66.     updateLongestPalindrome();
  67.     for (int i = 1; i <= N; ++i) {
  68.         int l = i, r = i;
  69.         while (l > 1 && r < N && isPal[l-1][r+1]) { l--; r++; }
  70.         tryExpand(l, r);
  71.  
  72.         l = i; r = i-1;
  73.         while (l > 1 && r < N && isPal[l-1][r+1]) { l--; r++; }
  74.         tryExpand(l, r);
  75.     }
  76. }
  77.  
  78. int main() {
  79.     ios::sync_with_stdio(false);
  80.     cin.tie(nullptr);
  81.  
  82.     cin >> N >> C;
  83.     for (int i = 1; i <= N; ++i) {
  84.         cin >> A[i];
  85.         freq[A[i]]++;
  86.         ans = max(ans, freq[A[i]]); // 한 문자만 반복되는 회문
  87.     }
  88.  
  89.     // 원본 방향
  90.     solveDirection();
  91.     // 뒤집어서 대칭 방향
  92.     reverse(A+1, A+N+1);
  93.     for (int i = 1; i <= N; ++i) A[i] = C - A[i] + 1;
  94.     solveDirection();
  95.  
  96.     cout << ans << "\n";
  97.     return 0;
  98. }
Success #stdin #stdout 0s 5308KB
comments (?)
stdin 
12 26
26
17
17
17
1
26
1
17
19
20
1
14
stdout 
5
https://ideone.com/4xNqlj
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!