oj.uz

Submission #1852

# Submission time Handle Problem Language Result Execution time Memory
1852 2013-07-19T02:31:21 Z alephnull 대표 선수 (KOI11_player) C++
20 / 20
 397 ms 4740 KB 
#include <cstdio>
#include <algorithm>
#include <ctime>
#include <utility>
#include <vector>
#include <functional>
using namespace std;
int main(){
	//freopen("input.txt","r",stdin);
 	//clock_t start_time, end_time;

    //start_time = clock();
    int n,m;scanf("%d %d",&n,&m);
    int *a[1000];
    for(int i=0;i<n;i++)a[i]=new int[1000];
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            scanf("%d",&a[i][j]);
    for(int i=0;i<n;i++)
        sort(a[i],a[i]+m);

    int ans=987654321;
    int p[1000];
    for(int i=0;i<n;i++)p[i]=0;
    pair<int,int> tmp[1000];
    for(int i=0;i<n;i++)tmp[i]=make_pair(a[i][p[i]],i);
    int max=0;
    for(int i=0;i<n;i++)if(max<a[i][p[i]])max=a[i][p[i]];
    vector<pair<int,int> >min(tmp,tmp+n);
    make_heap(min.begin(),min.end(),greater<pair<int,int> >());
    while(1){
    	if(ans>max-min.front().first)ans=max-min.front().first;
    	int idx=min.front().second;
    	if(p[idx]==m-1)break;
    	//printf("%d %d\n",idx,p[idx]);
    	p[idx]++;
    	if(a[idx][p[idx]]>max)max=a[idx][p[idx]];
    	pop_heap (min.begin(),min.end(),greater<pair<int,int> >()); min.pop_back();
    	min.push_back(make_pair(a[idx][p[idx]],idx)); push_heap(min.begin(),min.end(),greater<pair<int,int> >());
    }
    //end_time = clock();
    //printf("Time : %f\n", ((double)(end_time-start_time)) / CLOCKS_PER_SEC);
    printf("%d\n",ans);

}

Subtask #1
4.0 / 4.0

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

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1176 KB Output is correct
2 Correct 8 ms 1440 KB Output is correct
3 Correct 31 ms 1968 KB Output is correct
4 Correct 81 ms 2628 KB Output is correct
5 Correct 85 ms 2760 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 3024 KB Output is correct
2 Correct 100 ms 2892 KB Output is correct
3 Correct 151 ms 3420 KB Output is correct
4 Correct 173 ms 3288 KB Output is correct
5 Correct 191 ms 3684 KB Output is correct
6 Correct 231 ms 3684 KB Output is correct
7 Correct 306 ms 4212 KB Output is correct
8 Correct 258 ms 4080 KB Output is correct
9 Correct 299 ms 4608 KB Output is correct
10 Correct 397 ms 4740 KB Output is correct