ごり押しで何とかいけそうな問題。

ソートをして少し考察しましょう。

JOIの解説の通りにバケットソートを用いて解きました。

問題文の言われたとおりにやっただけなので解説は省かせてもらいます。


#include <cstdio>
#include <algorithm>

using namespace std;

int main(){

  int n,k;
  
  bool d[100002],flag = false;
  int ans = 0;
  
  scanf("%d%d",&n,&k);
  
  for(int i = 0;i < n;i++){
    d[i] = false;
  }
  
  for(int i = 0;i < k;i++){
    int t;
    scanf("%d",&t);
    d[t] = true;
  }
  
  if(d[0] == false){
    int ren = 0;
    for(int i = 1;i <= n;i++){
      if(d[i] == true){
	ren++;
      }else{
	ans = max(ans,ren);
	ren = 0;
      }
    }
    ans = max(ans,ren);
  }else{
    
    int rened = 0;
    int ren = 0;
    
    for(int i = 1;i <= n;i++){
      if(d[i] == false){
	ans = max(ans,rened+1+ren);
	rened = ren;
	ren = 0;
      }else{
	ren++;
      }
    }
    ans = max(ans,rened+1+ren);
  }
  
  printf("%d
",ans);

  return 0;
  
}