내용

글번호 927
작성자 허진경
작성일 2018-10-26 20:12:00
제목 그래도 시간이 절반은...
내용 그래도 시간이 절반은...
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
import java.io.FileInputStream;
import java.util.Scanner;
 
class 그래도시간이절반은
{
  public static void main(String args[]) throws Exception
  {
 
    //System.setIn(new FileInputStream("input.txt"));
 
    Scanner sc = new Scanner(System.in);
    int T;
    T=sc.nextInt();
     
    for(int test_case = 1; test_case <= T; test_case++)
    {
      int N = sc.nextInt();
      int K = sc.nextInt();
 
      int[] W = new int[N];
      int[] S = new int[K];
 
      for(int i=0; i<N; i++) {
        W[i] = sc.nextInt();
      }
      for(int i=0; i<K; i++) {
        S[i] = sc.nextInt();
      }
 
//      //입력 데이터 출력
//      for(int i=0; i<N; i++) {
//        System.out.printf("%2d ", W[i]);
//      }
//      System.out.println();
//      for(int i=0; i<K; i++) {
//        System.out.print(S[i] + " ");
//      }
//      System.out.println();
       
      //블록별 마모수준이 가장 큰 값을 저장
      int[][] block_sum = new int[K][N];
      for(int i=0; i<K; i++) {
        for(int j=0; j<=N-S[i]; j++) {
          int max = Integer.MIN_VALUE;
          for(int k=j; k<j+S[i]; k++) {
            if( max < W[k] )
              max = W[k];
          }
          block_sum[i][j] = max;
        }
      }
 
//      System.out.println("\n블록별 마모 수준");
//      for(int i=0; i<K; i++) {
//        for(int j=0; j<=N-S[i]; j++) {
//          System.out.printf("%2d ", block_sum[i][j]);
//        }
//        System.out.println();
//      }
//      System.out.println();
       
      int min_index = 0;
      int max_wear_level = Integer.MIN_VALUE;
      for(int i=0; i<K; i++) {
        int min_block_wear_level = Integer.MAX_VALUE;
        for(int j=min_index; j<=N-S[i]; j++) {
          if(min_block_wear_level > block_sum[i][j]) {
            min_block_wear_level = block_sum[i][j];
            min_index = i+S[i];
          }
        }
        if(max_wear_level<min_block_wear_level)
          max_wear_level = min_block_wear_level;
//        System.out.printf("-%d %d\n", block[i], min_block_wear_level);
      }
      System.out.println("#"+ test_case + " " + max_wear_level);
    }
    sc.close();
  }
}