C++(g++ 7.5.0) 解法, 执行用时: 70ms, 内存消耗: 1452K, 提交时间: 2023-03-12 21:44:29

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10;
int main(){
	int n,m,a[N],i,sum=0,l;
	scanf("%d%d",&n,&m);
	a[0]=0;
	for(i=1;i<=m;i++){
		scanf("%d",&a[i]);
	}
	a[m+1]=n;
	int k=sqrt(n);
	for(l=0;l<=k;l++){
		for(i=1;i+l<=m+1;i++){
			sum=max(sum,a[i+l]-a[i-1]-l*l);
		}
	}
	printf("%d",sum);
}

C++(clang++ 11.0.1) 解法, 执行用时: 53ms, 内存消耗: 796K, 提交时间: 2023-05-02 13:49:02

#include<bits/stdc++.h>
using namespace std;
int a[200010];
int main()
{
	int  n,m;cin>>n>>m;
	for(int i=1;i<=m;i++) cin>>a[i];
	a[++m]=n;
	int s=0;
	for(int i=0;i<min(500,m);i++)
	{
		for(int j=i+1;j<=m;j++)
			s=max(s,a[j]-a[j-i-1]-i*i);
	}
	cout<<s<<endl;
	return 0;
}

pypy3 解法, 执行用时: 303ms, 内存消耗: 32012K, 提交时间: 2023-02-10 23:32:04

n,m=map(int,input().split())
A=list(map(int,input().split()))
A=[0]+A
A.append(n)
ret=0
for i in range(1,501):
    if i-1>m:
        break
    for j in range(0,m+2-i):
        ret=max(ret,A[j+i]-A[j]-(i-1)**2)
print(ret)