#include<iostream> #include<algorithm> #include<cstring> #include<map> #include<vector> usingnamespace std; #define int long long typedeflonglong ll; int n; constint N = 5e3 + 7; int a[N]; int dp[N][N]; signedmain(){ scanf("%lld",&n); for ( int i = 1; i <= n; i ++) scanf("%lld", a + i); sort(a + 1,a + 1 + n); int ans = 0; for (int i = 2; i < n; i ++ ) { for (int j = 1 ; j < i;j ++ ) { int po = lower_bound(a + 1,a + 1 + n,2*a[i] - a[j]) - a; if (a[po] + a[j] == 2*a[i]) dp[po][i] = max(dp[i][j] + 1,dp[po][i]); } } for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= n; j ++ ) ans = max(ans, dp[i][j]); cout << ans + 2 << endl; }
#include<iostream> #include<algorithm> #include<cstring> #include<map> #include<vector> usingnamespace std; #define int long long typedeflonglong ll; int n; constint N = 1e5 + 7; int tr[N],a[N],tr2[N]; ll L[N],R[N],R2[N],L2[N]; ll ask(int x){ ll ans = 0; for (; x ;x -= x &-x) ans += tr[x]; return ans; } voidadd(int x,int v){ for (; x <= N; x += x &-x) tr[x] += v; } signedmain(){ int maxc = 0,minc = 0x3f3f3f3f; cin >> n;for (int i = 1; i <= n ; i ++ ) { int x; scanf("%lld", &x); a[i] = x; maxc = max(maxc,x); minc = min(minc,x); } for (int i = n ; i >= 1 ;i -- ) { int x = a[i]; ll res = ask(x - 1); R[i] = res; R2[i] = max(0ll,ask(100000) - ask(x)); add(x,1); } memset(tr,0,sizeof tr); for (int i = 1; i <= n; i ++ ) { int x = a[i]; ll res = ask(x - 1); L[i] = res; L2[i] = max(ask(100000) - ask(x),0ll); add(x,1); } int mincc = 0x3f3f3f3f, sum= 0; int ans = 0; for (int i = 1; i <= n; i ++ ) { //cout << a[i] << ' ' << L2[i] << ' ' << R2[i] << endl; ans += min(L2[i],R2[i]); } cout << ans << endl; }