oj.uz

Submission #16414

# Submission time Handle Problem Language Result Execution time Memory
16414 2015-08-23T04:49:33 Z comet 대표 선수 (KOI11_player) C++
20 / 20
 387 ms 5008 KB 
#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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5008 KB Output is correct
2 Correct 0 ms 5008 KB Output is correct
3 Correct 0 ms 5008 KB Output is correct
4 Correct 0 ms 5008 KB Output is correct
5 Correct 0 ms 5008 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5008 KB Output is correct
2 Correct 11 ms 5008 KB Output is correct
3 Correct 36 ms 5008 KB Output is correct
4 Correct 96 ms 5008 KB Output is correct
5 Correct 119 ms 5008 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 5008 KB Output is correct
2 Correct 113 ms 5008 KB Output is correct
3 Correct 165 ms 5008 KB Output is correct
4 Correct 166 ms 5008 KB Output is correct
5 Correct 206 ms 5008 KB Output is correct
6 Correct 228 ms 5008 KB Output is correct
7 Correct 290 ms 5008 KB Output is correct
8 Correct 312 ms 5008 KB Output is correct
9 Correct 329 ms 5008 KB Output is correct
10 Correct 387 ms 5008 KB Output is correct