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