oj.uz

Submission #1001

# Submission time Handle Problem Language Result Execution time Memory
1001 2013-06-15T02:04:32 Z tncks0121 대표 선수 (KOI11_player) C++
20 / 20
 268 ms 8904 KB 
#include<stdio.h>
#include<algorithm>
 
using namespace std;
 
#define N_ 1000
int N, M;
struct S1{
    int x, dat;
    bool operator< (const S1 &t) const { return dat < t.dat; }
}D[N_*N_+1];
 
int Chk [N_+1], cnt;
int res = 2147483647;
 
int main(){
    int i, j;
 
    scanf("%d%d",&N,&M);
    for(i=1; i<=N; i++){
        for(j=1; j<=M; j++){
            int v = (i-1) * M + j;
            scanf("%d",&D[v].dat);
            D[v].x = i;
        }
    }
    sort(D+1, D+N*M+1);
 
    Chk[D[1].x] ++; cnt ++;
    for(i=j=1; i<=N*M && j<=N*M; ){
        if(cnt == N){
            if(D[j].dat - D[i].dat < res) res = D[j].dat - D[i].dat;
            if(Chk[D[i].x] == 1) cnt --; 
            Chk[D[i].x] --; i++;
            continue;
        }
        if(Chk[D[i].x] > 1 && i+1 <= j){ Chk[D[i].x] --; i++; }
        else{
            j++; if(!Chk[D[j].x]) cnt++;
            Chk[D[j].x]++;
        }
    }
    printf("%d\n",res);
    return 0;
}

Subtask #1
4.0 / 4.0

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

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 8904 KB Output is correct
2 Correct 4 ms 8904 KB Output is correct
3 Correct 20 ms 8904 KB Output is correct
4 Correct 52 ms 8904 KB Output is correct
5 Correct 64 ms 8904 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 8904 KB Output is correct
2 Correct 72 ms 8904 KB Output is correct
3 Correct 88 ms 8904 KB Output is correct
4 Correct 124 ms 8904 KB Output is correct
5 Correct 124 ms 8904 KB Output is correct
6 Correct 160 ms 8904 KB Output is correct
7 Correct 204 ms 8904 KB Output is correct
8 Correct 196 ms 8904 KB Output is correct
9 Correct 220 ms 8904 KB Output is correct
10 Correct 268 ms 8904 KB Output is correct