結果

問題 No.2095 High Rise
ユーザー kyawakyawa
提出日時 2022-10-07 22:03:35
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 486 ms / 2,000 ms
コード長 2,003 bytes
コンパイル時間 2,398 ms
コンパイル使用メモリ 207,400 KB
実行使用メモリ 34,816 KB
最終ジャッジ日時 2023-09-03 12:34:02
合計ジャッジ時間 6,560 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 1 ms
4,380 KB
testcase_06 AC 1 ms
4,380 KB
testcase_07 AC 1 ms
4,376 KB
testcase_08 AC 1 ms
4,380 KB
testcase_09 AC 2 ms
4,376 KB
testcase_10 AC 2 ms
4,376 KB
testcase_11 AC 2 ms
4,376 KB
testcase_12 AC 3 ms
4,376 KB
testcase_13 AC 3 ms
4,380 KB
testcase_14 AC 4 ms
4,376 KB
testcase_15 AC 3 ms
4,376 KB
testcase_16 AC 2 ms
4,376 KB
testcase_17 AC 54 ms
7,564 KB
testcase_18 AC 35 ms
5,652 KB
testcase_19 AC 9 ms
4,376 KB
testcase_20 AC 61 ms
8,056 KB
testcase_21 AC 116 ms
10,984 KB
testcase_22 AC 482 ms
34,816 KB
testcase_23 AC 486 ms
34,740 KB
testcase_24 AC 482 ms
34,744 KB
testcase_25 AC 484 ms
34,692 KB
testcase_26 AC 483 ms
34,720 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

template<class S, S (*op)(S, S), S (*e)()>
class SegmentTree{
public:
    vector<S> table;
    int64_t size = 1;
    SegmentTree(vector<S> vec){
        while(size < vec.size()) size <<= 1;
        table.resize(size << 1, e());
        for(int64_t i = 0; i < (int64_t)vec.size(); i++) table[i + size] = vec[i];
        for(int64_t i = size - 1; i >= 1; i--) table[i] = op(table[i<<1|0],table[i<<1|1]);
    }
    SegmentTree(int64_t siz){
        while(size < siz) size <<= 1;
        table.resize(size << 1, e());
        for(int64_t i = 0; i < siz; i++) table[i + size] = e();
        for(int64_t i = size - 1; i >= 1; i--) table[i] = op(table[i<<1|0],table[i<<1|1]);
    }
    S fold(int64_t l, int64_t r){
        l += size; r += size;
        S Lres = e(), Rres = e();
        while(l < r){
            if(l & 1) Lres = op(Lres, table[l++]);
            if(r & 1) Rres = op(table[--r], Rres);
            l >>= 1; r >>= 1;
        }
        return op(Lres, Rres);
    }
    void set(int64_t p, S x){
        p += size;
        table[p] = x;
        while(p >>= 1) table[p] = op(table[p<<1|0],table[p<<1|1]);
    }
};

int64_t op(int64_t a, int64_t b){
    return  min(a, b);
}

int64_t e(){
    return INT64_MAX;
}

int main(){
    int64_t N, M; cin >> N >> M;
    vector A(N, vector(M, int64_t())); for(auto &v : A) for(auto &a : v) cin >> a;
    if(N == 1){
        cout << 0 << '\n';
        return 0;
    }
    vector dp(N, vector(M, INT64_MAX));
    vector<SegmentTree<int64_t, op, e>> seg(N, SegmentTree<int64_t, op, e>(M));
    for(int64_t j = 0; j < M; j++){
        dp[0][j] = A[0][j];
    }
    for(int64_t i = 1; i < N; i++){
        for(int64_t j = 0; j < M; j++){
            seg[i].set(j, A[i][j] + dp[i-1][j]);
        }
        for(int64_t j = 0; j < M; j++){
            dp[i][j] = A[i][j] + min(dp[i-1][j], min(seg[i].fold(0, j), seg[i].fold(j, M)));
        }
    }
    cout << *min_element(dp[N-1].begin(), dp[N-1].end()) << '\n';
}
0