oj.uz

Submission #4907

# Submission time Handle Problem Language Result Execution time Memory
4907 2014-01-09T11:32:43 Z gs13068 대표 선수 (KOI11_player) C++
20 / 20
 460 ms 12928 KB 
#include<cstdio>
#include<algorithm>
#include<set>

struct student
{
	int x;
	int y;
	int z;
} s[1000][1000],t;

inline bool operator <(const student &a,const student &b)
{
	if(a.x!=b.x)return a.x<b.x;
	if(a.y!=b.y)return a.y<b.y;
	return a.z<b.z;
}

std::set<student> S;
std::set<student>::iterator it1,it2;

int main()
{
	int min=1e9;
	int i,j,n,m;
	scanf("%d%d",&n,&m);
	for(i=0;i<n;i++)
	{
		for(j=0;j<m;j++)
		{
			scanf("%d",&s[i][j].x);
			s[i][j].y=i;
		}
		std::sort(s[i],s[i]+m);
	}
	for(i=0;i<n;i++)for(j=0;j<m;j++)s[i][j].z=j;
	for(i=0;i<n;i++)S.insert(s[i][0]);
	for(i=n;i<n*m;i++)
	{
		it1=S.begin();
		it2=S.end();
		it2--;
		if(it2->x-it1->x<min)
			min=it2->x-it1->x;
		if(it1->z+1==m)break;
		S.insert(s[it1->y][it1->z+1]);
		S.erase(it1);
	}
	printf("%d",min);
}

Subtask #1
4.0 / 4.0

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

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 12928 KB Output is correct
2 Correct 12 ms 12928 KB Output is correct
3 Correct 36 ms 12928 KB Output is correct
4 Correct 96 ms 12928 KB Output is correct
5 Correct 120 ms 12928 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 12928 KB Output is correct
2 Correct 128 ms 12928 KB Output is correct
3 Correct 164 ms 12928 KB Output is correct
4 Correct 192 ms 12928 KB Output is correct
5 Correct 232 ms 12928 KB Output is correct
6 Correct 264 ms 12928 KB Output is correct
7 Correct 340 ms 12928 KB Output is correct
8 Correct 344 ms 12928 KB Output is correct
9 Correct 404 ms 12928 KB Output is correct
10 Correct 460 ms 12928 KB Output is correct