1
1
// Authored by : keyboardmunji
2
2
// Co-authored by : -
3
- // http://boj.kr/e0c5f4a5d5fc4c8bae9107590e538eae
4
- #include < bits/stdc++.h>
3
+ // http://boj.kr/904f8aa97bd644f9a0633199b5cf6285
4
+ #include < bits/stdc++.h>
5
+ using namespace std ;
6
+
5
7
#define X first
6
8
#define Y second
7
9
8
- using namespace std ;
9
10
int n, m, cnt, en, ans = 0x7f7f7f7f ;
10
- int chk[1005 ]; // 각 팀이 구간속에 모두 있는지 확인하는 벡터
11
- vector<pair<int , int >> a; // 능력치와 각팀의 인덱스를 저장하는 벡터
11
+ int chk[1005 ]; // 각 팀이 구간속에 모두 있는지 확인하는 벡터
12
+ vector<pair<int , int >> a; // 능력치와 각팀의 인덱스를 저장하는 벡터
12
13
13
14
int main (void ) {
14
- ios::sync_with_stdio (false );
15
- cin.tie (NULL );
15
+ ios::sync_with_stdio (0 );
16
+ cin.tie (0 );
16
17
17
- cin >> n >> m;
18
- for (int i = 0 ;i < n;i++) {
19
- for (int j = 0 ;j < m;j++) {
20
- int num;
21
- cin >> num;
22
- a.push_back ({ num, i });
23
- }
18
+ cin >> n >> m;
19
+ for (int i = 0 ; i < n; i++) {
20
+ for (int j = 0 ; j < m; j++) {
21
+ int num;
22
+ cin >> num;
23
+ a.push_back ({num, i});
24
24
}
25
- sort (a.begin (), a.end ());
25
+ }
26
+ sort (a.begin (), a.end ());
26
27
27
- for (int st = 0 ;st < n * m;st++) {
28
- // 구간 속에 각 팀이 모두 포함되게 en을 증가
29
- while (cnt < n && en < n * m) {
30
- if (chk[a[en].Y ] == 0 )
31
- cnt++;
32
- chk[a[en].Y ]++;
33
- en++;
34
- }
35
- if (cnt != n)
36
- break ;
37
- ans = min (ans, a[en - 1 ].X - a[st].X );
38
- chk[a[st].Y ]--;
39
- if (chk[a[st].Y ] == 0 )
40
- cnt--;
28
+ for (int st = 0 ; st < n * m; st++) {
29
+ // 구간 속에 각 팀이 모두 포함되게 en을 증가
30
+ while (cnt < n && en < n * m) {
31
+ if (chk[a[en].Y ] == 0 ) cnt++;
32
+ chk[a[en].Y ]++;
33
+ en++;
41
34
}
42
- cout << ans;
43
- return 0 ;
44
- }
35
+ if (cnt != n) break ;
36
+ ans = min (ans, a[en - 1 ].X - a[st].X );
37
+ chk[a[st].Y ]--;
38
+ if (chk[a[st].Y ] == 0 ) cnt--;
39
+ }
40
+ cout << ans;
41
+ return 0 ;
42
+ }
0 commit comments