LEM5 - ARITHMETIC PROGRESSION

Tác giả: ladpro98

Ngôn ngữ: C++

#include <bits/stdc++.h>
#define X first
#define Y second
const int N = 100005;
const int oo = 1000000009;
const int lim = 100;
using namespace std;
int n, res, f[N], b[N];
pair<int, int> a[N], u;
int main()
{
    scanf("%d", &n);
    int i, j, pos, res = 0, v;
    for(i=1; i<=n; i++) {
        scanf("%d", &v);
        a[i] = make_pair(v, i);
    }
    sort(a+1, a+n+1);

    for(j=1; j<=lim; j++) {
        pos = 0; for(i=1; i<=n; i++) f[i] = 1;
        for(i=2; i<=n; i++) {
            u = pair<int, int> (a[i].X - j, a[i].Y);
            while (pos < n && a[pos + 1] <= u) pos++;
            if (a[pos].X == u.X && a[pos].Y < u.Y)
                f[i] = f[pos] + 1;
            res = max(res, f[i]);
        }
    }
    printf("%d", res);
    return 0;
}

Download