fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int N, C, A[3009], U[3009], ans;
  5. bool D[3009][3009];
  6.  
  7. void go(int s, int e) {
  8.     if (s < 0 || N < e || s > e) return;
  9.  
  10.     int p = -1;
  11.     vector<int> T;
  12.     for (int i = s - 1; i >= 1; i--) {
  13.         if (p == -1 || p <= A[i]) {
  14.             T.push_back(A[i]);
  15.             p = A[i];
  16.         } else break;
  17.     }
  18.  
  19.     int l = 0, r = (int)T.size() - 1;
  20.     while (l <= r) {
  21.         int m = (l + r) >> 1;
  22.         vector<int> H(C + 1, 0);
  23.         for (int i = 0; i <= m; i++) ++H[T[i]];
  24.         int c = 0;
  25.         bool f = 1, sr = 1;
  26.         for (int i = e + 1; i <= N && c <= m; i++) {
  27.             if (H[A[i]]) {
  28.                 --H[A[i]];
  29.                 ++c;
  30.             } else {
  31.                 sr = 0;
  32.                 if (A[i] < T[m]) f = 0;
  33.             }
  34.         }
  35.         f &= (c > m);
  36.  
  37.         if (f) {
  38.             int L = s - m - 1, R = e + m + 1;
  39.             if (sr) while (L - 1 >= 1 && R + 1 <= N && A[L - 1] == A[R + 1]) --L, ++R;
  40.             ans = max(ans, R - L + 1);
  41.         }
  42.  
  43.         if (f) l = m + 1;
  44.         else r = m - 1;
  45.     }
  46. }
  47.  
  48. void Do(int s, bool SR) {
  49.     int p = -1;
  50.     vector<int> T;
  51.     for (int i = s - 1; i >= 1; i--) {
  52.         if (p == -1 || p <= A[i]) {
  53.             T.push_back(A[i]);
  54.             p = A[i];
  55.         } else break;
  56.     }
  57.     if (T.empty()) return;
  58.  
  59.     int mn = T[0];
  60.     for (int i = s; i <= N; i++) if (T[0] > A[i]) { mn = A[i]; break; }
  61.  
  62.     int l = 0, r = (int)T.size() - 1;
  63.     while (l <= r) {
  64.         int m = (l + r) >> 1;
  65.         vector<int> H(C + 1, 0);
  66.         for (int i = 0; i <= m; i++) ++H[T[i]];
  67.         int c = 0, mnc = 0;
  68.         bool f = 1, sr = 1;
  69.         for (int i = s; i <= N; i++) {
  70.             if (H[A[i]]) {
  71.                 --H[A[i]];
  72.                 ++c;
  73.             } else if (A[i] == mn) ++mnc;
  74.             else {
  75.                 if (sr && SR && c > m) break;
  76.                 sr = 0;
  77.                 if (A[i] < T[m]) break;
  78.             }
  79.         }
  80.         f &= (c > m);
  81.  
  82.         if (f) {
  83.             int L = s - m - 1, R = s + m + mnc;
  84.             if (sr) while (L - 1 >= 1 && R + 1 <= N && A[L - 1] == A[R + 1]) --L, ++R;
  85.             ans = max(ans, R - L + 1);
  86.         }
  87.  
  88.         if (f) l = m + 1;
  89.         else r = m - 1;
  90.     }
  91. }
  92.  
  93. void solve() {
  94.     for (int i = N; i >= 1; i--) {
  95.         for (int j = i; j <= N; j++) {
  96.             if (i + 1 >= j && A[i] == A[j]) D[i][j] = 1;
  97.             else if (D[i + 1][j - 1] && A[i] == A[j]) D[i][j] = 1;
  98.             else D[i][j] = 0;
  99.             if (D[i][j]) ans = max(ans, j - i + 1);
  100.         }
  101.     }
  102.     for (int i = 1; i <= N; i++) {
  103.         int l = i, r = i;
  104.         while (l - 1 >= 1 && r + 1 <= N && D[l - 1][r + 1]) --l, ++r;
  105.         go(l, r);
  106.         l = i; r = i - 1;
  107.         while (l - 1 >= 1 && r + 1 <= N && D[l - 1][r + 1]) --l, ++r;
  108.         go(l, r);
  109.         Do(i, 0);
  110.         Do(i, 1);
  111.     }
  112. }
  113.  
  114. int main() {
  115.     scanf("%d%d", &N, &C);
  116.     A[0] = 1000000000;
  117.     for (int i = 1; i <= N; i++) {
  118.         scanf("%d", &A[i]);
  119.         ++U[A[i]];
  120.     }
  121.     for (int i = 1; i <= C; i++) ans = max(ans, U[i]);
  122.     solve();
  123.     reverse(A + 1, A + N + 1);
  124.     for (int i = 1; i <= N; i++) A[i] = C - A[i] + 1;
  125.     solve();
  126.     printf("%d\n", ans);
  127.     return 0;
  128. }
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
4 3
1
2
3
2
stdout
copy 
3
https://ideone.com/afHbCa
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!