Submission #1852

#	Time	Username	Problem	Language	Result	Execution time	Memory
1852		alephnull	대표 선수 (KOI11_player)	C++98	20 / 20	397 ms	4740 KiB

player

#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 / 4
• Subtask 2: 6 / 6
• Subtask 3: 10 / 10