結果

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

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 2 ms
4,384 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 1 ms
4,376 KB
testcase_04 AC 1 ms
4,380 KB
testcase_05 AC 1 ms
4,380 KB
testcase_06 AC 2 ms
4,376 KB
testcase_07 AC 1 ms
4,380 KB
testcase_08 AC 2 ms
4,376 KB
testcase_09 AC 2 ms
4,380 KB
testcase_10 AC 1 ms
4,376 KB
testcase_11 AC 2 ms
4,380 KB
testcase_12 AC 2 ms
4,376 KB
testcase_13 AC 1 ms
4,380 KB
testcase_14 AC 2 ms
4,376 KB
testcase_15 AC 2 ms
4,380 KB
testcase_16 AC 2 ms
4,380 KB
testcase_17 AC 5 ms
4,380 KB
testcase_18 AC 4 ms
4,376 KB
testcase_19 AC 2 ms
4,380 KB
testcase_20 AC 5 ms
4,376 KB
testcase_21 AC 9 ms
4,376 KB
testcase_22 AC 36 ms
4,376 KB
testcase_23 AC 35 ms
4,380 KB
testcase_24 AC 35 ms
4,376 KB
testcase_25 AC 35 ms
4,376 KB
testcase_26 AC 35 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

namespace nachia{

const unsigned int INPUT_BUF_SIZE = 1 << 17;
const unsigned int OUTPUT_BUF_SIZE = 1 << 17;

char input_buf[INPUT_BUF_SIZE];

struct InputBufIterator{
private:
    unsigned int p = INPUT_BUF_SIZE;
public:
    using MyType = InputBufIterator;
    char seekChar(){
        if(p == INPUT_BUF_SIZE){
            size_t len = fread(input_buf, 1, INPUT_BUF_SIZE, stdin);
            if(len != INPUT_BUF_SIZE) input_buf[len] = '\0';
            p = 0;
        }
        return input_buf[p];
    }
    void skipWhitespace(){ while(isspace(seekChar())) p++; }
    unsigned int nextUint(){
        skipWhitespace();
        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(){
        skipWhitespace();
        if(seekChar() == '-'){
            p++;
            return (int)(-nextUint());
        }
        return (int)nextUint();
    }
    unsigned long long nextUlong(){
        skipWhitespace();
        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(){
        skipWhitespace();
        if(seekChar() == '-'){
            p++;
            return (long long)(-nextUlong());
        }
        return (long long)nextUlong();
    }
    char nextChar(){
        skipWhitespace();
        char buf = seekChar();
        p++;
        return buf;
    }
    std::string nextToken(){
        skipWhitespace();
        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; }
};


char output_buf[OUTPUT_BUF_SIZE] = {};

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

struct OutputBufIterator{
    using u32 = uint_fast32_t;
    using u64 = uint_fast64_t;
    using MyType = OutputBufIterator;
    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); }
    void nextChar(char c){
        output_buf[p++] = c;
        if(p == OUTPUT_BUF_SIZE){
            fwrite(output_buf, p, 1, stdout);
            p = 0;
        }
    }
    void next_eoln(){ nextChar('\n'); }
    void nextCstr(const char* s){ while(*s) nextChar(*(s++)); }
    void next_dig9(u32 x){
        u32 y;
        y = x / POW10(6); x -= y * POW10(6);
        nextCstr(TB.LZ[y]);
        y = x / POW10(3); x -= y * POW10(3);
        nextCstr(TB.LZ[y]);
        y = x;
        nextCstr(TB.LZ[y]);
    }
    void nextUint(unsigned int x){
        unsigned int y = 0;
        if(x >= POW10(9)){
            y = x / POW10(9); x -= y * POW10(9);
            nextCstr(TB.NLZ[y]);
            next_dig9(x);
        }
        else if(x >= POW10(6)){
            y = x / POW10(6); x -= y * POW10(6);
            nextCstr(TB.NLZ[y]);
            y = x / POW10(3); x -= y * POW10(3);
            nextCstr(TB.LZ[y]);
            nextCstr(TB.LZ[x]);
        }
        else if(x >= POW10(3)){
            y = x / POW10(3); x -= y * POW10(3);
            nextCstr(TB.NLZ[y]);
            nextCstr(TB.LZ[x]);
        }
        else if(x >= 1){
            nextCstr(TB.NLZ[x]);
        }
        else{
            nextChar('0');
        }
    }
    void nextInt(int x){
        if(x >= 0) nextUint(x);
        else{
            nextChar('-');
            nextUint((unsigned int)-x);
        }
    }
    void nextUlong(unsigned long long x){
        u32 y = 0;
        if(x >= POW10LL(18)){
            y = x / POW10LL(18); x -= y * POW10LL(18);
            nextUint(y);
            y = x / POW10LL(9); x -= y * POW10LL(9);
            next_dig9(y);
            next_dig9(x);
        }
        else if(x >= POW10LL(9)){
            y = x / POW10LL(9); x -= y * POW10LL(9);
            nextUint(y);
            next_dig9(x);
        }
        else{
            nextUint(x);
        }
    }
    void nextLong(long long x){
        if(x >= 0) nextUlong(x);
        else{
            nextChar('-');
            nextUlong((unsigned long long)-x);
        }
    }
    void writeToFile(bool flush = false){
        fwrite(output_buf, p, 1, stdout);
        if(flush) fflush(stdout);
        p = 0;
    }
    ~OutputBufIterator(){ writeToFile(); }
    MyType& operator<<(unsigned int tg){ nextUint(tg); return *this; }
    MyType& operator<<(unsigned long tg){ nextUlong(tg); return *this; }
    MyType& operator<<(unsigned long long tg){ nextUlong(tg); return *this; }
    MyType& operator<<(int tg){ nextInt(tg); return *this; }
    MyType& operator<<(long tg){ nextLong(tg); return *this; }
    MyType& operator<<(long long tg){ nextLong(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; }
};

} // 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