LEM5 - ARITHMETIC PROGRESSION

Tác giả: skyvn97

Ngôn ngữ: C++

#include<algorithm>
#include<cstdio>
#include<map>
#include<vector>
#define MAXN   100100
#define MAXD   100
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
#define fi   first
#define se   second
using namespace std;
int a[MAXN],pos[MAXN];
pair<vector<int>,int>* add[MAXN][MAXD+7];
map<int,pair<vector<int>,int> > haveVal;
int f[MAXN][MAXD];
int n;
void init(void) {
    scanf("%d",&n);
    FOR(i,1,n) scanf("%d",&a[i]);
}
bool CompPos(const int &x,const int &y) {
    return (a[x]<a[y]);
}
bool findVal(int &id,int val) {
    while (id>=1 && a[pos[id]]>val) id--;
    return (id>=1 && a[pos[id]]==val);
}
void prepare(void) {
    FOR(i,1,n) pos[i]=i;
    sort(pos+1,pos+n+1,CompPos);
    FOR(i,1,n) haveVal[a[i]].fi.push_back(i);
    for (map<int,pair<vector<int>,int> >::iterator it=haveVal.begin();it!=haveVal.end();it++) it->se.se=0;
    FOR(i,1,n) {
        int curPos=pos[i];
        int prevPos=pos[i-1];
        int id=i;
        FOR(k,1,MAXD) {
            if (i>1 && a[prevPos]-1>=a[curPos]-k) add[curPos][k]=add[prevPos][a[prevPos]-a[curPos]+k];
            else add[curPos][k]=findVal(id,a[curPos]-k)?&haveVal[a[curPos]-k]:NULL;
        }
    }
}
int getLastPos(int i,int j) {
    if (add[i][j]==NULL) return (-1);
    vector<int> &cur=add[i][j]->fi;
    int &id=add[i][j]->se;
    while (id<cur.size() && cur[id]<i) id++;
    return (id==0?-1:cur[id-1]);
}
void optimize(void) {
    int res=0;
    FOR(i,1,n) FOR(j,1,MAXD) {
        int k=getLastPos(i,j);
        if (k<1) f[i][j]=1; else f[i][j]=f[k][j]+1;
        res=max(res,f[i][j]);
    }
    printf("%d\n",res);
}
int main(void) {
    init();
    prepare();
    optimize();
    return 0;
}

Download