概述
垃圾题目卡老子常数
不过题目本身还是可以的
当长度大的时候,值相邻最近的就小;
当长度小的时候,值相邻最近的就大。
哪个小我们枚举哪个
卡卡常就能过
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#define N 200050
using namespace std;
typedef int LL;
int f[N][2];
int n,m,k,a[N],tmp[N],cur[N],s;
inline int Abs(int x) { return x<0 ? -x : x; }
inline void utax(int &x,int y) { y>x?x=y:0; }
inline void utin(int &x,int y) { y<x?x=y:0; }
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
LL get1() {
LL ret = 0;
for (int i=0;i<=n;++i) f[i][0] = f[i][1] = (1<<30);
for (int _=1;_<=s;++_)
for (int i=_+1;i<=n;++i) {
f[i][_&1] = min(f[i][_&1^1] , f[i-1][_&1^1]);
utin( f[i][_&1] , Abs(a[i]-a[i-_]) );
if (_+1 >= k) ret = max( ret , _ * f[i][_&1] );
}
return ret;
}
LL get2() {
LL ret = 0; int lim = m/(s-1);
for (int _=0;_<=lim;++_) {
for (int i=1;i<=m;++i) tmp[i] = 0;
for (int i=1;i<=n;++i) {
if (a[i]-_ >= 1) utax(cur[i] , tmp[ a[i] - _ ]);
if (a[i]+_ <= m) utax(cur[i] , tmp[ a[i] + _ ]);
tmp[a[i]] = i;
}
for (int h=0,t=0;h<=n;) {
if (t-h+1 >= k) ret = max(ret,(t-h) * (_+1));
++h;
while (cur[t+1] < h && t<n) t++;
}
}
return ret;
}
int main() {
// freopen("1.in","r",stdin);
n = read(); m = read(); k = read();
if (k > n) { puts("0"); return 0; }
for (int i=1;i<=n;++i) a[i] = read();
s = 2 * sqrt(m);
LL ans = max(get1() , get2());
printf("%lldn",ans);
return 0;
}
最后
以上就是自然雪糕为你收集整理的[UOJ246]套路 分类讨论+卡常的全部内容,希望文章能够帮你解决[UOJ246]套路 分类讨论+卡常所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复