結果

問題 No.2095 High Rise
ユーザー 👑 NachiaNachia
提出日時 2022-10-07 22:32:44
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 34 ms / 2,000 ms
コード長 6,696 bytes
コンパイル時間 759 ms
コンパイル使用メモリ 83,208 KB
実行使用メモリ 4,500 KB
最終ジャッジ日時 2023-09-03 13:48:46
合計ジャッジ時間 2,793 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 2 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 2 ms
4,384 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 1 ms
4,380 KB
testcase_10 AC 2 ms
4,376 KB
testcase_11 AC 1 ms
4,376 KB
testcase_12 AC 1 ms
4,380 KB
testcase_13 AC 2 ms
4,380 KB
testcase_14 AC 2 ms
4,376 KB
testcase_15 AC 2 ms
4,376 KB
testcase_16 AC 1 ms
4,380 KB
testcase_17 AC 6 ms
4,380 KB
testcase_18 AC 4 ms
4,380 KB
testcase_19 AC 2 ms
4,380 KB
testcase_20 AC 6 ms
4,380 KB
testcase_21 AC 9 ms
4,500 KB
testcase_22 AC 34 ms
4,380 KB
testcase_23 AC 33 ms
4,380 KB
testcase_24 AC 33 ms
4,376 KB
testcase_25 AC 33 ms
4,376 KB
testcase_26 AC 33 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#line 2 "nachia\\misc\\fastio.hpp"
#include <cstdio>
#include <cctype>
#include <cstdint>
#include <string>

namespace nachia{

struct InputBufIterator{
private:
    static const unsigned int INPUT_BUF_SIZE = 1 << 17;
    unsigned int p = INPUT_BUF_SIZE;
    static char Q[INPUT_BUF_SIZE];
public:
    using MyType = InputBufIterator;
    char seekChar(){
        if(p == INPUT_BUF_SIZE){
            size_t len = fread(Q, 1, INPUT_BUF_SIZE, stdin);
            if(len != INPUT_BUF_SIZE) Q[len] = '\0';
            p = 0;
        }
        return Q[p];
    }
    void skipSpace(){ while(isspace(seekChar())) p++; }
    uint32_t nextU32(){
        skipSpace();
        uint32_t buf = 0;
        while(true){
            char tmp = seekChar();
            if('9' < tmp || tmp < '0') break;
            buf = buf * 10 + (tmp - '0');
            p++;
        }
        return buf;
    }
    int32_t nextI32(){
        skipSpace();
        if(seekChar() == '-'){ p++; return (int32_t)(-nextU32()); }
        return (int32_t)nextU32();
    }
    uint64_t nextU64(){
        skipSpace();
        uint64_t buf = 0;
        while(true){
            char tmp = seekChar();
            if('9' < tmp || tmp < '0') break;
            buf = buf * 10 + (tmp - '0');
            p++;
        }
        return buf;
    }
    int64_t nextI64(){
        skipSpace();
        if(seekChar() == '-'){ p++; return (int64_t)(-nextU64()); }
        return (int64_t)nextU64();
    }
    char nextChar(){ skipSpace(); char buf = seekChar(); p++; return buf; }
    std::string nextToken(){
        skipSpace();
        std::string buf;
        while(true){
            char ch = seekChar();
            if(isspace(ch) || ch == '\0') break;
            buf.push_back(ch);
            p++;
        }
        return buf;
    }
    MyType& operator>>(unsigned int& dest){ dest = nextU32(); return *this; }
    MyType& operator>>(int& dest){ dest = nextI32(); return *this; }
    MyType& operator>>(unsigned long& dest){ dest = nextU64(); return *this; }
    MyType& operator>>(long& dest){ dest = nextI64(); return *this; }
    MyType& operator>>(unsigned long long& dest){ dest = nextU64(); return *this; }
    MyType& operator>>(long long& dest){ dest = nextI64(); return *this; }
    MyType& operator>>(std::string& dest){ dest = nextToken(); return *this; }
    MyType& operator>>(char& dest){ dest = nextChar(); return *this; }
} cin;

struct FastOutputTable{
    char LZ[1000][4] = {};
    char NLZ[1000][4] = {};
    constexpr FastOutputTable(){
        using u32 = uint_fast32_t;
        for(u32 d=0; d<1000; d++){
            LZ[d][0] = ('0' + d / 100 % 10);
            LZ[d][1] = ('0' + d /  10 % 10);
            LZ[d][2] = ('0' + d /   1 % 10);
            LZ[d][3] = '\0';
        }
        for(u32 d=0; d<1000; d++){
            u32 i = 0;
            if(d >= 100) NLZ[d][i++] = ('0' + d / 100 % 10);
            if(d >=  10) NLZ[d][i++] = ('0' + d /  10 % 10);
            if(d >=   1) NLZ[d][i++] = ('0' + d /   1 % 10);
            NLZ[d][i++] = '\0';
        }
    }
};

char InputBufIterator::Q[INPUT_BUF_SIZE];

struct OutputBufIterator{
private:
    using u32 = uint32_t;
    using u64 = uint64_t;
    using MyType = OutputBufIterator;
    static const u32 OUTPUT_BUF_SIZE = 1 << 17;
    static char Q[OUTPUT_BUF_SIZE];
    static constexpr FastOutputTable TB = FastOutputTable();
    u32 p = 0;
    static constexpr u32 P10(u32 d){ return d ? P10(d-1)*10 : 1; }
    static constexpr u64 P10L(u32 d){ return d ? P10L(d-1)*10 : 1; }
    template<class T, class U> static void Fil(T& m, U& l, U x) noexcept { m = l/x; l -= m*x; }
    void next_dig9(u32 x){
        u32 y;
        Fil(y, x, P10(6));
        nextCstr(TB.LZ[y]);
        Fil(y, x, P10(3));
        nextCstr(TB.LZ[y]); nextCstr(TB.LZ[x]);
    }
public:
    void nextChar(char c){
        Q[p++] = c;
        if(p == OUTPUT_BUF_SIZE){ fwrite(Q, p, 1, stdout); p = 0; }
    }
    void next_eoln(){ nextChar('\n'); }
    void nextCstr(const char* s){ while(*s) nextChar(*(s++)); }
    void nextU32(uint32_t x){
        u32 y = 0;
        if(x >= P10(9)){
            Fil(y, x, P10(9));
            nextCstr(TB.NLZ[y]); next_dig9(x);
        }
        else if(x >= P10(6)){
            Fil(y, x, P10(6));
            nextCstr(TB.NLZ[y]);
            Fil(y, x, P10(3));
            nextCstr(TB.LZ[y]); nextCstr(TB.LZ[x]);
        }
        else if(x >= P10(3)){
            Fil(y, x, P10(3));
            nextCstr(TB.NLZ[y]); nextCstr(TB.LZ[x]);
        }
        else if(x >= 1) nextCstr(TB.NLZ[x]);
        else nextChar('0');
    }
    void nextI32(int32_t x){
        if(x >= 0) nextU32(x);
        else{ nextChar('-'); nextU32((u32)-x); }
    }
    void nextU64(uint64_t x){
        u32 y = 0;
        if(x >= P10L(18)){
            Fil(y, x, P10L(18));
            nextU32(y);
            Fil(y, x, P10L(9));
            next_dig9(y); next_dig9(x);
        }
        else if(x >= P10L(9)){
            Fil(y, x, P10L(9));
            nextU32(y); next_dig9(x);
        }
        else nextU32(x);
    }
    void nextI64(int64_t x){
        if(x >= 0) nextU64(x);
        else{ nextChar('-'); nextU64((u64)-x); }
    }
    void writeToFile(bool flush = false){
        fwrite(Q, p, 1, stdout);
        if(flush) fflush(stdout);
        p = 0;
    }
    OutputBufIterator(){ Q[0] = 0; }
    ~OutputBufIterator(){ writeToFile(); }
    MyType& operator<<(unsigned int tg){ nextU32(tg); return *this; }
    MyType& operator<<(unsigned long tg){ nextU64(tg); return *this; }
    MyType& operator<<(unsigned long long tg){ nextU64(tg); return *this; }
    MyType& operator<<(int tg){ nextI32(tg); return *this; }
    MyType& operator<<(long tg){ nextI64(tg); return *this; }
    MyType& operator<<(long long tg){ nextI64(tg); return *this; }
    MyType& operator<<(const std::string& tg){ nextCstr(tg.c_str()); return *this; }
    MyType& operator<<(const char* tg){ nextCstr(tg); return *this; }
    MyType& operator<<(char tg){ nextChar(tg); return *this; }
} cout;

char OutputBufIterator::Q[OUTPUT_BUF_SIZE];

} // namespace nachia
#line 2 "Main.cpp"
#include <vector>
#include <algorithm>
#define rep(i,n) for(int i=0; i<(int)(n); i++)

int main(){
    nachia::InputBufIterator cin;
    nachia::OutputBufIterator cout;
    int N, M; cin >> N >> M;
    std::vector<long long> dp(M, 0);
    std::vector<long long> A(M, 0);
    rep(i,N){
        rep(j,M) cin >> A[j];
        rep(j,M) dp[j] += A[j];
        long long mdp = *std::min_element(dp.begin(), dp.end());
        rep(j,M) dp[j] = std::min(dp[j], mdp + A[j]);
    }
    long long ans = *std::min_element(dp.begin(), dp.end());
    if(N == 1) ans = 0;
    cout << ans << '\n';
    return 0;
}
0