解法
sqrt(500000000)までの素数を全て求め，その素数に対し4乗によって作れる数，それに3乗素数を足して作れる数，それに2乗素数を足して作れる数，のように順番に求めていく．
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int bufsize=512;
char buf[bufsize];
int bufcount=bufsize;
int getcharc(){
if(bufcount==bufsize){
fread(buf,sizeof(char),bufsize,stdin);bufcount=0;
}
return buf[bufcount++];
}
int readuint(){
int res=0;
char buf[1];
*buf=0;
*buf=getcharc();
while(!(*buf>='0'&&*buf<='9'))*buf=getcharc();
while(*buf>='0'&&*buf<='9'){
res*=10;res+=*buf-'0';
*buf=getcharc();
}
return res;
}
typedef pair<int,int> P;
P data[100000];
int a[100001];
int ans=0;
int N,L;
int main() {
N=readuint();L=readuint();
for(int i=0;i<N;i++){
data[i].first=L-readuint();
data[i].second=i;
}
std::sort(data,data+N);
for(int i=0;i<N;i++){
a[data[i].second+1]=max<int>(a[data[i].second],a[data[i].second+2])+data[i].first;
ans=max(ans,a[data[i].second+1]);
}
printf("%d\n",ans);
return 0;
}
