zoj 3790
1453 ワード
スキャンします.
const int maxn = 100008 ;
int x[maxn] , c[maxn] ;
int n , k ;
vector <int> g[maxn] ;
int main(){
int i , m , t , d , L , R , a ;
while(cin>>n>>k){
for(i = 0 ; i < n ; i++){
scanf("%d" , &c[i]) ;
x[i] = c[i] ;
}
sort(x , x+n) ;
m = unique(x , x+n) - x ;
for(i = 0 ; i < n ; i++)
c[i] = upper_bound(x , x+m , c[i]) - x ;
for(i = 1 ; i <= m ; i++) g[i].clear() ;
for(i = 0 ; i < n ; i++)
g[c[i]].push_back(i) ;
int s = 1 ;
for(a = 1 ; a <= m ; a++){
t = 1 ;
d = k ;
L = 0 ;
for(R = 1 ; R < g[a].size() ; R++){
if(g[a][R] - g[a][R-1] == 1){
t++ ;
s = max(s , t) ;
continue ;
}
d -= g[a][R] - g[a][R-1] - 1 ;
if(d >= 0){
t++ ;
s = max(s , t) ;
}
else{
while(d < 0){
L++ ;
d += g[a][L] - g[a][L-1] - 1 ;
t-- ;
}
t++ ;
}
}
}
cout<< s <<endl ;
}
return 0;
}