結果

問題 No.2095 High Rise
コンテスト
ユーザー kyawa
提出日時 2022-10-07 22:03:35
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 564 ms / 2,000 ms
コード長 2,003 bytes
コンパイル時間 2,085 ms
コンパイル使用メモリ 204,192 KB
最終ジャッジ日時 2025-02-07 23:24:45
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

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