Submission #16414

#	Time	Username	Problem	Language	Result	Execution time	Memory
16414		comet	대표 선수 (KOI11_player)	C++98	20 / 20	387 ms	5008 KiB

player

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
struct player{
	int x,v;
	bool operator<(const player& r)const{
		return x<r.x;
	}
}s[2000];
int n,m,a[1000][1000];
int sz,z,L,R,ans=1e9;
int chk[1000],cnt;
int main(){

	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			scanf("%d",&a[i][j]);
		}
		sort(a[i],a[i]+m);
	}

	for(int i=0;i<m;i++){
		sz=cnt=0;
		memset(chk,0,sizeof(chk));
		s[sz++]=player{a[0][i],0};
		for(int j=1;j<n;j++){
			z=lower_bound(a[j],a[j]+m,a[0][i])-a[j];
			if(z>0)
				s[sz++]=player{a[j][z-1],j};
			if(z<m)
				s[sz++]=player{a[j][z],j};
		}
		sort(s,s+sz);
		L=0;
		R=-1;
		while(1){
			while(cnt<n){
				R++;
				if(R==sz)break;
				chk[s[R].v]++;
				if(chk[s[R].v]==1)cnt++;
			}
			if(R==sz)break;
			while(cnt==n){
				ans=min(ans,s[R].x-s[L].x);
				chk[s[L].v]--;
				if(chk[s[L].v]==0)cnt--;
				L++;
			}
		}
	}
	printf("%d",ans);
}

• Subtask 1: 4 / 4
• Subtask 2: 6 / 6
• Subtask 3: 10 / 10