結果

問題 No.335 門松宝くじ
コンテスト
ユーザー asi1024
提出日時 2016-02-20 22:05:37
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 203 ms / 2,000 ms
コード長 1,991 bytes
コンパイル時間 1,562 ms
コンパイル使用メモリ 169,228 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-22 12:30:34
合計ジャッジ時間 3,712 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()

using namespace std;

struct Data {
  int mi, ma;
  Data() : mi(0x7FFFFFFF), ma(0x80000000) {;}
  Data(int n) : mi(n), ma(n) {;}
  Data(int mi, int ma) : mi(mi), ma(ma) {;}
};

inline Data Merge(Data left, Data right) {
  return Data(min(left.mi, right.mi), max(left.ma, right.ma));
}

struct SegmentTree {
  int n; vector<Data> data;
  SegmentTree(int N) : n(1 << N), data(n * 2) {}
  void update (int pos, Data value) {
    data[pos] = value;
    while (pos < 2*n-1) {
      int l = pos, r = pos^1;
      if (l > r) swap(l, r);
      pos = pos / 2 + n;
      data[pos] = Merge(data[l], data[r]);
    }
  }
  Data sub(int fr, int to, int node, int la, int ra) {
    if (ra<=fr || to<=la) return Data();
    if (fr<=la && ra<=to) return data[node];
    Data vl = sub(fr, to, (node-n)*2+0, la, (la+ra)/2);
    Data vr = sub(fr, to, (node-n)*2+1, (la+ra)/2, ra);
    return Merge(vl, vr);
  }
  Data query(int fr, int to) { return sub(fr, to, 2*n-2, 0, n); }
};

int solve(int N) {
  SegmentTree seg(10);
  vector<int> a(N);
  REP(i,N) {
    cin >> a[i];
    seg.update(i, a[i]);
  }
  int res = 0;
  REP(i,N) REP(j,i) {
    Data left = seg.query(0, j);
    Data mid = seg.query(j+1, i);
    Data right = seg.query(i+1, N);
    int val = 0;
    if (left.ma > a[j] && a[j] < a[i])  val = max({val, left.ma, a[i]});
    if (left.mi < a[j] && a[j] > a[i])  val = max(val, a[j]);
    if (a[j] > mid.mi && mid.mi < a[i]) val = max({val, a[j], a[i]});
    if (a[j] < mid.ma && mid.ma > a[i]) val = max(val, mid.ma);
    if (a[j] > a[i] && a[i] < right.ma) val = max({val, a[j], right.ma});
    if (a[j] < a[i] && a[i] > right.mi) val = max(val, a[i]);
    res += val;
  }
  return res;
}

int main() {
  int N, M; cin >> N >> M;
  int ma = 0, res = 0;
  REP(i,M) {
    int v = solve(N);
    //cout << v << endl;
    if (v > ma) { ma = v; res = i; }
  }
  cout << res << endl;
  return 0;
}
0