fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int N, C;
  5. int seq[3010];       // 입력 수열
  6. int countVal[3010];  // 값 개수 카운트
  7. int prefixSum[3010]; // 누적합
  8. int matchLen[3010][3010];
  9. int ans;
  10.  
  11. void extendPalindrome() {
  12.     // matchLen[i][j] 계산: i~j 범위에서 양쪽으로 확장 가능한 길이
  13.     for (int i = 1; i <= N; i++) {
  14.         for (int j = N; j >= i; j--) {
  15.             matchLen[i][j] = 0;
  16.             if (seq[i-1] == seq[j+1] && i > 1 && j < N)
  17.                 matchLen[i][j] = matchLen[i-1][j+1] + 1;
  18.         }
  19.     }
  20.  
  21.     // 각 위치를 중심으로 확장
  22.     for (int center = 1; center < N; center++) {
  23.         int left = center;
  24.         set<int> S;
  25.         fill(countVal, countVal+C+1, 0);
  26.         countVal[seq[left]]++;
  27.         S.insert(seq[left]);
  28.  
  29.         // 왼쪽 확장
  30.         while (left > 1 && seq[left-1] >= seq[left]) {
  31.             left--;
  32.             countVal[seq[left]]++;
  33.             S.insert(seq[left]);
  34.         }
  35.  
  36.         // 오른쪽 확장
  37.         int smallVal = -1, smallCount = 0;
  38.         for (int right = center+1; right <= N; right++) {
  39.             if (seq[center] > seq[right]) {
  40.                 if (smallVal != -1) {
  41.                     if (smallVal == seq[right]) smallCount++;
  42.                     else break;
  43.                 } else {
  44.                     smallVal = seq[right];
  45.                     smallCount = 1;
  46.                 }
  47.             } else {
  48.                 if (!countVal[seq[right]]) S.insert(seq[right]);
  49.                 countVal[seq[right]]--;
  50.                 if (!countVal[seq[right]]) S.erase(seq[right]);
  51.             }
  52.  
  53.             int last = C;
  54.             if (!S.empty()) last = *S.begin();
  55.             else ans = max(ans, right - left + 1 + matchLen[left][right]*2);
  56.  
  57.             ans = max(ans,
  58.                       prefixSum[last-1]*2 +
  59.                       (prefixSum[last] - prefixSum[last-1] + min(0, -countVal[last]))*2 +
  60.                       smallCount);
  61.         }
  62.     }
  63.  
  64.     // 중심 기준으로 홀수/짝수 길이 확장
  65.     for (int sum = 2; sum <= N+N; sum++) {
  66.         int b = sum/2 + 1, e = sum - sum/2 - 1;
  67.         while (b > 1 && e < N && seq[b-1] == seq[e+1]) b--, e++;
  68.         int bb = b-1;
  69.         fill(countVal, countVal+C+1, 0);
  70.         set<int> S;
  71.  
  72.         ans = max(ans, e-b+1);
  73.         if (b == 1) continue;
  74.  
  75.         int be = bb;
  76.         for (int j = bb; j >= 1; j--) {
  77.             if (j != bb && seq[j] < seq[j+1]) break;
  78.             be = j;
  79.             countVal[seq[j]]++;
  80.             S.insert(seq[j]);
  81.         }
  82.  
  83.         for (int j = 1; j <= C; j++) {
  84.             prefixSum[j] = countVal[j];
  85.             prefixSum[j] += prefixSum[j-1];
  86.         }
  87.  
  88.         for (int j = e+1; j <= N; j++) {
  89.             if (seq[bb] > seq[j]) break;
  90.             if (!countVal[seq[j]]) S.insert(seq[j]);
  91.             countVal[seq[j]]--;
  92.             if (!countVal[seq[j]]) S.erase(seq[j]);
  93.  
  94.             int last = C;
  95.             if (!S.empty()) last = *S.begin();
  96.             else ans = max(ans, j-be+1 + matchLen[be][j]*2);
  97.  
  98.             ans = max(ans,
  99.                       prefixSum[last-1]*2 +
  100.                       (prefixSum[last]-prefixSum[last-1]+min(0, -countVal[last]))*2 +
  101.                       e-b+1);
  102.         }
  103.     }
  104. }
  105.  
  106. int solve() {
  107.     ans = 0;
  108.     fill(countVal, countVal+C+1, 0);
  109.     for (int i = 1; i <= N; i++) {
  110.         countVal[seq[i]]++;
  111.         ans = max(ans, countVal[seq[i]]);
  112.     }
  113.  
  114.     extendPalindrome();
  115.     reverse(seq+1, seq+N+1);
  116.     for (int i = 1; i <= N; i++) seq[i] = C + 1 - seq[i];
  117.     extendPalindrome();
  118.     return ans;
  119. }
  120.  
  121. int main() {
  122.     ios::sync_with_stdio(false);
  123.     cin.tie(nullptr);
  124.  
  125.     cin >> N >> C;
  126.     for (int i = 1; i <= N; i++) cin >> seq[i];
  127.     cout << solve() << "\n";
  128. }
Success #stdin #stdout 0.01s 5684KB
comments (?)
stdin 
12 26
26
17
17
17
1
26
1
17
19
20
1
14
stdout 
8
https://ideone.com/nLdKOq
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!