记录编号	513315	评测结果	AAAAA
题目名称	简单题kewu	最终得分	100
用户昵称	胡嘉兴	是否通过	通过
代码语言	C++	运行时间	3.426 s
提交时间	2018-10-10 12:50:55	内存使用	19.41 MiB

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;
const int N = 5e3+7, M = 1e6+7;
int a[N], p[M], siz[M];
vector<pair<int, int> > vec[M];
inline void add(pair<int, int> t)
{
    siz[0] -= siz[p[t.fi]]/2;
    siz[p[t.fi]] += siz[t.se];
    siz[0] += siz[p[t.fi]]/2;
    p[t.se] = p[t.fi];
    return;
}
inline void update(pair<int, int> t)
{
    p[t.fi] = t.fi;
    p[t.se] = t.se;
    siz[t.fi] = siz[t.se] = 1;
    return;
}
inline void reduction(int x, int l, int r)
{
    siz[0] = 0;
    for(int i = x; i < l; i += x)
    {
        for(int j = 0; j < vec[i].size(); j++)
        {
            update(vec[i][j]);
        }
    }
    for(int i = 0; i < r; i++)
    {
        update(vec[l][i]);
    }
    return;
}
inline bool check(int x, int n, int k)
{
    int l, r;
    for(int i = x; i <= n; i += x)
    {
        l = i;
        r = vec[i].size();
        for(int j = 0; j < vec[i].size(); j++)
        {
            add(vec[i][j]);
            if(siz[0]>k)
            {
                reduction(x, i, j+1);
                return false;
            }
        }
    }
    reduction(x, l, r);
    return true;
}
int main()
{
    int n, k;
    //freopen("test.in", "r", stdin);
    freopen("kewu.in", "r", stdin);
    freopen("kewu.out", "w", stdout);
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
    }
    sort(a+1, a+1+n);
    for(int i = 1; i < M; i++)
    {
        p[i] = i;
        siz[i] = 1;
    }
    for(int i = 1; i <= n; i++)
    {
        for(int j = i+1; j <= n; j++)
        {
            vec[a[j]-a[i]].push_back(make_pair(i, j));
        }
    }
    for(int i = n-1; i <= a[n]; i++)
    {
        if(check(i, a[n], k))
        {
            printf("%d\n", i);
            break;
        }
    }
    return 0;
}