結果

問題 No.335 門松宝くじ
ユーザー asi1024asi1024
提出日時 2016-02-20 22:05:37
言語 C++11
(gcc 11.4.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 1 ms
6,812 KB
testcase_02 AC 1 ms
6,940 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 2 ms
6,944 KB
testcase_05 AC 56 ms
6,940 KB
testcase_06 AC 82 ms
6,940 KB
testcase_07 AC 135 ms
6,944 KB
testcase_08 AC 131 ms
6,940 KB
testcase_09 AC 202 ms
6,944 KB
testcase_10 AC 203 ms
6,944 KB
testcase_11 AC 203 ms
6,940 KB
testcase_12 AC 202 ms
6,944 KB
testcase_13 AC 202 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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