結果
| 問題 |
No.2095 High Rise
|
| コンテスト | |
| ユーザー |
 Nachia
|
| 提出日時 | 2022-10-07 22:23:17 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 35 ms / 2,000 ms |
| コード長 | 7,015 bytes |
| コンパイル時間 | 974 ms |
| コンパイル使用メモリ | 79,524 KB |
| 最終ジャッジ日時 | 2025-02-07 23:33:55 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 24 |
ソースコード
#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;
}