oj.uz

Submission #16412

# Submission time Handle Problem Language Result Execution time Memory
16412 2015-08-23T04:38:00 Z comet 대표 선수 (KOI11_player) C++
3.6 / 20
 386 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;
		/*printf("%d : ",i);
		for(int j=0;j<sz;j++)printf("%d ",s[j]);
		puts("");*/
		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;
			ans=min(ans,s[R].x-s[L].x);
			while(cnt==n){
				chk[s[L].v]--;
				if(chk[s[L].v]==0)cnt--;
				L++;
			}
		}
	}
	printf("%d",ans);
}

Subtask #1
1.6 / 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 Incorrect 0 ms 5008 KB Output isn't correct
4 Incorrect 0 ms 5008 KB Output isn't correct
5 Incorrect 0 ms 5008 KB Output isn't correct

Subtask #2
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 5008 KB Output isn't correct
2 Incorrect 13 ms 5008 KB Output isn't correct
3 Incorrect 31 ms 5008 KB Output isn't correct
4 Incorrect 80 ms 5008 KB Output isn't correct
5 Incorrect 128 ms 5008 KB Output isn't correct

Subtask #3
2.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 111 ms 5008 KB Output isn't correct
2 Correct 125 ms 5008 KB Output is correct
3 Correct 160 ms 5008 KB Output is correct
4 Incorrect 201 ms 5008 KB Output isn't correct
5 Incorrect 214 ms 5008 KB Output isn't correct
6 Incorrect 212 ms 5008 KB Output isn't correct
7 Incorrect 267 ms 5008 KB Output isn't correct
8 Incorrect 285 ms 5008 KB Output isn't correct
9 Incorrect 317 ms 5008 KB Output isn't correct
10 Incorrect 386 ms 5008 KB Output isn't correct