結果

問題 No.335 門松宝くじ
ユーザー roarisroaris
提出日時 2019-12-11 18:31:54
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 691 ms / 2,000 ms
コード長 2,835 bytes
コンパイル時間 1,861 ms
コンパイル使用メモリ 181,092 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-09-06 13:08:13
合計ジャッジ時間 7,843 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 172 ms
4,380 KB
testcase_06 AC 256 ms
4,376 KB
testcase_07 AC 460 ms
4,380 KB
testcase_08 AC 456 ms
4,376 KB
testcase_09 AC 687 ms
4,380 KB
testcase_10 AC 688 ms
4,376 KB
testcase_11 AC 687 ms
4,380 KB
testcase_12 AC 689 ms
4,380 KB
testcase_13 AC 691 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define INF 2000000000

int my_min(int a, int b) {
    if (a<b) return a;
    else return b;
}

int my_max(int a, int b) {
    if (a>b) return a;
    else return b;
}

struct SegmentTree {
    int n;
    function<int(int, int)> func;
    int ele;
    vector<int> arr;
    
    SegmentTree(int N, int (*f)(int, int), int e) {
        int n_ = 1;
        while (n_<N) {
            n_ *= 2;
        }
        n = n_;
        func = f;
        ele = e;
        arr.resize(2*n-1);
        fill(arr.begin(), arr.end(), e);
    }
    
    void update(int k, int a) {
        k += n-1;
        arr[k] = a;
        while (k>0) {
            k = (k-1)/2;
            arr[k] = func(arr[2*k+1], arr[2*k+2]);
        }
    }
    
    int query_sub(int a, int b, int k, int l, int r) {
        if (r<=a || b<=l) return ele;
        
        if (a<=l && r<=b) return arr[k];
        else {
            int vl = query_sub(a, b, 2*k+1, l, (l+r)/2);
            int vr = query_sub(a, b, 2*k+2, (l+r)/2, r);
            return func(vl, vr);
        }
    }
    
    int query(int a, int b) {
        return query_sub(a, b, 0, 0, n);
    }
};

int main() {
    int N, M; cin >> N >> M;
    int v_max = -1;
    int ans = -1;
    
    for (int m=0; m<M; m++) {
        int E[N];
        SegmentTree st_min = SegmentTree(N, my_min, INF);
        SegmentTree st_max = SegmentTree(N, my_max, -INF);
        
        for (int i=0; i<N; i++) {
            cin >> E[i];
            E[i]--;
            st_min.update(i, E[i]);
            st_max.update(i, E[i]);
        }
        
        int v = 0;
        
        for (int i=0; i<N; i++) {
            for (int j=i+1; j<N; j++) {
                int prof = 0;
                int min_1 = st_min.query(0, i);
                int max_1 = st_max.query(0, i);
                int min_2 = st_min.query(i, j);
                int max_2 = st_max.query(i, j);
                int min_3 = st_min.query(j, N);
                int max_3 = st_max.query(j, N);
                
                if (E[i]>E[j]) {
                    if (min_1<E[i]) prof = max(prof, E[i]);
                    if (max_2>E[i]) prof = max(prof, max_2);
                    if (min_2<E[j]) prof = max(prof, E[i]);
                    if (max_3>E[j]) prof = max({prof, E[i], max_3});
                }
                else if (E[i]<E[j]) {
                    if (max_1>E[i]) prof = max({prof, max_1, E[j]});
                    if (min_2<E[i]) prof = max(prof, E[j]);
                    if (max_2>E[j]) prof = max(prof, max_2);
                    if (min_3<E[j]) prof = max(prof, E[j]);
                }
                
                v += prof;
            }
        }
        
        if (v_max<v) {
            v_max = v;
            ans = m;
        }
    }
    
    cout << ans << endl;
}
0