# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
16413 |
2015-08-23T04:49:09 Z |
comet |
대표 선수 (KOI11_player) |
C++ |
|
436 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;
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);
}
# |
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 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
5008 KB |
Output is correct |
2 |
Correct |
10 ms |
5008 KB |
Output is correct |
3 |
Correct |
33 ms |
5008 KB |
Output is correct |
4 |
Correct |
91 ms |
5008 KB |
Output is correct |
5 |
Correct |
106 ms |
5008 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
136 ms |
5008 KB |
Output is correct |
2 |
Correct |
119 ms |
5008 KB |
Output is correct |
3 |
Correct |
157 ms |
5008 KB |
Output is correct |
4 |
Correct |
162 ms |
5008 KB |
Output is correct |
5 |
Correct |
189 ms |
5008 KB |
Output is correct |
6 |
Correct |
252 ms |
5008 KB |
Output is correct |
7 |
Correct |
267 ms |
5008 KB |
Output is correct |
8 |
Correct |
313 ms |
5008 KB |
Output is correct |
9 |
Correct |
316 ms |
5008 KB |
Output is correct |
10 |
Correct |
436 ms |
5008 KB |
Output is correct |