fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int N, C;
  5. int A[3005], freq[3005];
  6. bool isPal[3005][3005];
  7. int ans = 0;
  8.  
  9. void calcPalindrome() {
  10.     for (int i = N; i >= 1; i--) {
  11.         for (int j = i; j <= N; j++) {
  12.             if (i == j) isPal[i][j] = true;
  13.             else if (i + 1 == j) isPal[i][j] = (A[i] == A[j]);
  14.             else isPal[i][j] = (A[i] == A[j] && isPal[i + 1][j - 1]);
  15.             if (isPal[i][j]) ans = max(ans, j - i + 1);
  16.         }
  17.     }
  18. }
  19.  
  20. void tryExtend(int L, int R) {
  21.     // L, R은 현재 회문 범위
  22.     vector<int> leftPart;
  23.     int prev = -1;
  24.     for (int i = L - 1; i >= 1; i--) {
  25.         if (prev == -1 || prev <= A[i]) {
  26.             leftPart.push_back(A[i]);
  27.             prev = A[i];
  28.         } else break;
  29.     }
  30.     if (leftPart.empty()) return;
  31.  
  32.     int lo = 0, hi = (int)leftPart.size() - 1;
  33.     while (lo <= hi) {
  34.         int mid = (lo + hi) / 2;
  35.         vector<int> cnt(C + 1, 0);
  36.         for (int i = 0; i <= mid; i++) cnt[leftPart[i]]++;
  37.  
  38.         int match = 0;
  39.         bool can = true, sortedRight = true;
  40.         for (int i = R + 1; i <= N && match <= mid; i++) {
  41.             if (cnt[A[i]]) {
  42.                 cnt[A[i]]--;
  43.                 match++;
  44.             } else {
  45.                 sortedRight = false;
  46.                 if (A[i] < leftPart[mid]) can = false;
  47.             }
  48.         }
  49.         can &= (match > mid);
  50.  
  51.         if (can) {
  52.             int newL = L - mid - 1;
  53.             int newR = R + mid + 1;
  54.             if (sortedRight) {
  55.                 while (newL > 1 && newR < N && A[newL - 1] == A[newR + 1]) {
  56.                     newL--;
  57.                     newR++;
  58.                 }
  59.             }
  60.             ans = max(ans, newR - newL + 1);
  61.             lo = mid + 1;
  62.         } else {
  63.             hi = mid - 1;
  64.         }
  65.     }
  66. }
  67.  
  68. void solveOnce() {
  69.     calcPalindrome();
  70.     for (int center = 1; center <= N; center++) {
  71.         int l = center, r = center;
  72.         while (l > 1 && r < N && isPal[l - 1][r + 1]) l--, r++;
  73.         tryExtend(l, r);
  74.  
  75.         l = center;
  76.         r = center - 1;
  77.         while (l > 1 && r < N && isPal[l - 1][r + 1]) l--, r++;
  78.         tryExtend(l, r);
  79.     }
  80. }
  81.  
  82. int main() {
  83.     ios::sync_with_stdio(false);
  84.     cin.tie(nullptr);
  85.  
  86.     cin >> N >> C;
  87.     for (int i = 1; i <= N; i++) {
  88.         cin >> A[i];
  89.         freq[A[i]]++;
  90.     }
  91.     for (int i = 1; i <= C; i++) ans = max(ans, freq[i]);
  92.  
  93.     solveOnce();
  94.  
  95.     reverse(A + 1, A + N + 1);
  96.     for (int i = 1; i <= N; i++) A[i] = C - A[i] + 1;
  97.     solveOnce();
  98.  
  99.     cout << ans << "\n";
  100. }
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
12 26
26
17
17
17
1
26
1
17
19
20
1
14
stdout
copy 
5
https://ideone.com/BQRlYJ
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!