結果

問題 No.2095 High Rise
ユーザー 👑 NachiaNachia
提出日時 2022-10-07 22:23:17
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 30 ms / 2,000 ms
コード長 7,015 bytes
コンパイル時間 804 ms
コンパイル使用メモリ 80,504 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-09-03 13:24:01
合計ジャッジ時間 2,693 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 2 ms
4,384 KB
testcase_02 AC 1 ms
4,384 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 2 ms
4,384 KB
testcase_05 AC 1 ms
4,380 KB
testcase_06 AC 1 ms
4,380 KB
testcase_07 AC 2 ms
4,380 KB
testcase_08 AC 1 ms
4,380 KB
testcase_09 AC 2 ms
4,384 KB
testcase_10 AC 1 ms
4,380 KB
testcase_11 AC 1 ms
4,384 KB
testcase_12 AC 1 ms
4,380 KB
testcase_13 AC 1 ms
4,380 KB
testcase_14 AC 1 ms
4,384 KB
testcase_15 AC 2 ms
4,384 KB
testcase_16 AC 1 ms
4,380 KB
testcase_17 AC 5 ms
4,380 KB
testcase_18 AC 4 ms
4,384 KB
testcase_19 AC 2 ms
4,384 KB
testcase_20 AC 5 ms
4,384 KB
testcase_21 AC 8 ms
4,384 KB
testcase_22 AC 29 ms
4,380 KB
testcase_23 AC 30 ms
4,380 KB
testcase_24 AC 30 ms
4,380 KB
testcase_25 AC 29 ms
4,384 KB
testcase_26 AC 30 ms
4,380 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++; }
    unsigned int nextUint(){
        skipSpace();
        unsigned int buf = 0;
        while(true){
            char tmp = seekChar();
            if('9' < tmp || tmp < '0') break;
            buf = buf * 10 + (tmp - '0');
            p++;
        }
        return buf;
    }
    int nextInt(){
        skipSpace();
        if(seekChar() == '-'){
            p++;
            return (int)(-nextUint());
        }
        return (int)nextUint();
    }
    unsigned long long nextUlong(){
        skipSpace();
        unsigned long long buf = 0;
        while(true){
            char tmp = seekChar();
            if('9' < tmp || tmp < '0') break;
            buf = buf * 10 + (tmp - '0');
            p++;
        }
        return buf;
    }
    long long nextLong(){
        skipSpace();
        if(seekChar() == '-'){
            p++;
            return (long long)(-nextUlong());
        }
        return (long long)nextUlong();
    }
    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 = nextUint(); return *this; }
    MyType& operator>>(int& dest){ dest = nextInt(); return *this; }
    MyType& operator>>(unsigned long& dest){ dest = nextUlong(); return *this; }
    MyType& operator>>(long& dest){ dest = nextLong(); return *this; }
    MyType& operator>>(unsigned long long& dest){ dest = nextUlong(); return *this; }
    MyType& operator>>(long long& dest){ dest = nextLong(); return *this; }
    MyType& operator>>(std::string& dest){ dest = nextToken(); return *this; }
    MyType& operator>>(char& dest){ dest = nextChar(); return *this; }
};

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 = uint_fast32_t;
    using u64 = uint_fast64_t;
    using MyType = OutputBufIterator;
    static const unsigned int OUTPUT_BUF_SIZE = 1 << 17;
    static char Q[OUTPUT_BUF_SIZE];
    static constexpr FastOutputTable TB = FastOutputTable();
    u32 p = 0;
    static constexpr u32 POW10(int d){ return (d<=0) ? 1 : (POW10(d-1)*10); }
    static constexpr u64 POW10LL(int d){ return (d<=0) ? 1 : (POW10LL(d-1)*10); }
    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, POW10(6));
        nextCstr(TB.LZ[y]);
        Fil(y, x, POW10(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(uint_fast32_t x){
        u32 y = 0;
        if(x >= POW10(9)){
            Fil(y, x, POW10(9));
            nextCstr(TB.NLZ[y]); next_dig9(x);
        }
        else if(x >= POW10(6)){
            Fil(y, x, POW10(6));
            nextCstr(TB.NLZ[y]);
            Fil(y, x, POW10(3));
            nextCstr(TB.LZ[y]); nextCstr(TB.LZ[x]);
        }
        else if(x >= POW10(3)){
            Fil(y, x, POW10(3));
            nextCstr(TB.NLZ[y]); nextCstr(TB.LZ[x]);
        }
        else if(x >= 1) nextCstr(TB.NLZ[x]);
        else nextChar('0');
    }
    void nextI32(int_fast32_t x){
        if(x >= 0) nextU32(x);
        else{
            nextChar('-');
            nextU32((u32)-x);
        }
    }
    void nextU64(uint_fast64_t x){
        u32 y = 0;
        if(x >= POW10LL(18)){
            Fil(y, x, POW10LL(18));
            nextU32(y);
            Fil(y, x, POW10LL(9));
            next_dig9(y); next_dig9(x);
        }
        else if(x >= POW10LL(9)){
            Fil(y, x, POW10LL(9));
            nextU32(y); next_dig9(x);
        }
        else nextU32(x);
    }
    void nextI64(long long 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; }
};

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