fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define pii pair<int, int>
  3. #define mp make_pair
  4.  
  5. using namespace std;
  6.  
  7. int n, a[2005], tmp[2005], upto[2005], post[2005], t = 0;
  8.  
  9. pii arr[2005];
  10.  
  11. void print(){
  12.     for(int j = 0; j < t; j++)
  13.         cout << "(" << arr[j].first << " " << arr[j].second << ")  ";
  14.     cout << endl;
  15. }
  16.  
  17. int rev(int l, int r){
  18.     for(int j = 0; j < n; j++)
  19.         tmp[j] = a[j];
  20.     for(int j = l; j <= (r + l)/2; j++)
  21.         swap(tmp[j], tmp[r + l - j]);
  22.  
  23.     t = 0;
  24.     for(int j = 0; j < n; j++){
  25.         int c = tmp[j], cnt = 0;
  26.         while(j < n && c == tmp[j]) cnt++, j++;
  27.         j--;
  28.         arr[t++] = mp(c, cnt);
  29.     }
  30.     //print();
  31.  
  32.     int ans = 0;
  33.     upto[t] = 0;
  34.     upto[t-1] = arr[t-1].second;
  35.     ans = upto[t-1];
  36.     for(int j = t-2; j >= 0; j--){
  37.         int cur = arr[j].second;
  38.         if(arr[j].first == 1) upto[j] = max(upto[j+2]+cur, upto[j+1]+cur);
  39.         else upto[j] = cur + upto[j+2];
  40.         if(ans < upto[j]) ans = upto[j];
  41.     }
  42.     //cout << l << " " << r << " " << ans << endl;
  43.     return ans;
  44. }
  45.  
  46. int main(){
  47.     scanf("%d",&n);
  48.     for(int j = 0; j < n; j++)
  49.         scanf("%d",&a[j]);
  50.     int ans = rev(0, 0);
  51.  
  52.     for(int j = 0; j < n; j++){
  53.         for(int k = j+1; k < n; k++){
  54.             ans = max(ans, rev(j, k));
  55.         }
  56.     }
  57.     printf("%d\n",ans);
  58.     return 0;
  59. }
Success #stdin #stdout 0s 4544KB
comments (?)
stdin
copy 
10
1 1 2 2 2 1 1 2 2 1
stdout
copy 
9
https://ideone.com/Nd1oiy
language:
C++14 (gcc 8.3)
created:
6 years 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!