제출 #5371

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
5371		baneling100	대표 선수 (KOI11_player)	C++98	20 / 20	308 ms	5124 KiB

player

#include <stdio.h>
#include <algorithm>
#include <queue>
#include <vector>
#define inf 0x7fffffff

using namespace std;

typedef pair <int,int> ppair;
priority_queue <ppair,vector<ppair>,greater<ppair> > q;
int n, m, a[1001][1001], ans=inf;

void input(void)
{
    int i, j;

    scanf("%d %d",&n,&m);
    for(i=1 ; i<=n ; i++)
    {
        for(j=1 ; j<=m ; j++)
            scanf("%d",&a[i][j]);
        sort(a[i]+1,a[i]+m+1);
    }
}

void process(void)
{
    int i, ptr[1001], mmax=-inf, mmin, minv;

    for(i=1 ; i<=n ; i++)
    {
        ptr[i]=1;
        q.push(make_pair(a[i][1],i));
        if(mmax<a[i][1])
            mmax=a[i][1];
    }
    while(1)
    {
        mmin=q.top().first;
        minv=q.top().second;
        q.pop();
        if(ans>mmax-mmin)
            ans=mmax-mmin;
        ptr[minv]++;
        if(ptr[minv]>m)
            break;
        q.push(make_pair(a[minv][ptr[minv]],minv));
        if(mmax<a[minv][ptr[minv]])
            mmax=a[minv][ptr[minv]];
    }
}

void output(void)
{
    printf("%d",ans);
}

int main(void)
{
    input();
    process();
    output();

    return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 6 / 6
• Subtask 3: 10 / 10