結果

問題 No.335 門松宝くじ
コンテスト
ユーザー takeya_okino
提出日時 2019-07-07 11:03:39
言語 Java
(openjdk 23)
結果
WA  
実行時間 -
コード長 2,030 bytes
コンパイル時間 1,900 ms
コンパイル使用メモリ 77,168 KB
実行使用メモリ 61,812 KB
最終ジャッジ日時 2024-10-04 07:02:19
合計ジャッジ時間 7,319 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 5 WA * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.*;

public class Main {
  static int N;
  static long[] dat1;
  static long[] dat2;

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    init(n);
    int m = sc.nextInt();
    long[] ki = new long[m];
    long ma = 0;

    for(int i = 0; i < m; i++) {
      long[] E = new long[n];
      for(int j = 0; j < n; j++) {
        E[j] = sc.nextLong();
        update(j, E[j]);
      }
      long t = 0;
      for(int j = 0; j < n - 1; j++) {
        for(int k = j + 1; k < n; k++) {
          long[] r = query(j, k + 1, 0, 0, N);
          if((r[1] > E[j]) && (r[1] > E[k])) t += r[1];
          if((r[0] < E[j]) && (r[0] < E[k])) t += (Math.max(E[j], E[k]));
        }
      }
      ki[i] = t;
      ma = Math.max(ma, t);
    }
    
    for(int i = 0; i < m; i++) {
      if(ki[i] == ma) {
        System.out.println(i);
        break; 
      }
    }
  }

  public static void init(int n_) {
    int n = 1;
    while(n < n_) {
      n *= 2;
    }
    N = n;
    dat1 = new long[2 * N - 1];
    dat2 = new long[2 * N - 1];
    for(int i = 0; i < dat1.length; i++) {
      dat1[i] = 100000;
      dat2[i] = (-1) * 100000;
    }
  }

  public static void update(int k, long x) {
    int a = k + N - 1;
    dat1[a] = x;
    dat2[a] = x;
    while(a > 0) {
      a = (a - 1) / 2;
      dat1[a] = Math.min(dat1[2 * a + 1], dat1[2 * a + 2]);
      dat2[a] = Math.max(dat2[2 * a + 1], dat2[2 * a + 2]);
    }
  }

  public static long[] query(int a, int b, int k, int l, int r) {
    long[] ret = new long[2];
    if((r <= a) || (l >= b)) {
      ret[0] = 100000;
      ret[1] = (-1) * 100000;
      return ret;
    }
    if((a <= l) && (r <= b)) {
      ret[0] = dat1[k];
      ret[1] = dat2[k];
      return ret;
    } else {
      long[] retl = query(a, b, 2 * k + 1, l, (l + r) / 2);
      long[] retr = query(a, b, 2 * k + 2, (l + r) / 2, r);
      ret[0] = Math.min(retl[0], retr[0]);
      ret[1] = Math.max(retl[1], retr[1]);
      return ret;
    }
  }
}
0