oj.uz

Submission #2141

# Submission time Handle Problem Language Result Execution time Memory
2141 2013-07-20T03:03:22 Z hana5505 대표 선수 (KOI11_player) C++
20 / 20
 369 ms 16940 KB 
#include<stdio.h> 
#include<deque> 
#include<algorithm> 
using namespace std; 
deque<int> ar[1001]; 
int size=0,aa[1000001]; 
struct pp{ 
    int score; 
    int team; 
}play[1000001]; 
bool cmp(struct pp a,struct pp b){ 
    return a.score<b.score; 
} 
int main() 
{ 
    //freopen("input.txt","r",stdin); 
    //freopen("output.txt","w",stdout); 
  
    int n,m,i,j,t,cnt=0,min,minindex,max,ans=1999999999; 
  
    scanf("%d %d",&n,&m); 
  
    for(i=1;i<=n;i++){ 
        for(j=1;j<=m;j++){ 
            size++; 
            scanf("%d",&play[size].score); 
            play[size].team=i; 
        } 
    } 
  
    sort(play+1,play+size+1,cmp); 
  
    for(i=1;i<=size;i++){ 
        ar[play[i].team].push_back(play[i].score); 
        aa[i]=play[i+1].team; 
    } 
  
    min=1999999999; 
    minindex=0; 
    max=-1; 
    t=1; 
    for(i=1;i<=n;i++){ 
        if(ar[i].front()>max) max=ar[i].front(); 
        if(ar[i].front()<min){ 
            min=ar[i].front(); 
            minindex=i; 
        } 
    } 
    if(ans>(max-min)) ans=(max-min); 
    ar[minindex].pop_front(); 
    if(ar[minindex].front()>max) max=ar[minindex].front(); 
    min=ar[aa[t]].front(); 
    minindex=aa[t]; 
    while(1){ 
        if(ans>(max-min)) ans=(max-min); 
        ar[minindex].pop_front(); 
        if(ar[minindex].size()<1) break; 
        if(ar[minindex].front()>max) max=ar[minindex].front(); 
        min=ar[aa[++t]].front(); 
        minindex=aa[t]; 
    } 
    printf("%d",ans); 
}

Subtask #1
4.0 / 4.0

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

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 13244 KB Output is correct
2 Correct 8 ms 13376 KB Output is correct
3 Correct 28 ms 13508 KB Output is correct
4 Correct 78 ms 13904 KB Output is correct
5 Correct 97 ms 14036 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 14300 KB Output is correct
2 Correct 105 ms 14300 KB Output is correct
3 Correct 139 ms 14564 KB Output is correct
4 Correct 159 ms 14960 KB Output is correct
5 Correct 182 ms 15224 KB Output is correct
6 Correct 217 ms 15224 KB Output is correct
7 Correct 269 ms 16016 KB Output is correct
8 Correct 276 ms 15884 KB Output is correct
9 Correct 325 ms 16280 KB Output is correct
10 Correct 369 ms 16940 KB Output is correct