結果
問題 | No.1199 お菓子配り-2 |
ユーザー | ningenMe |
提出日時 | 2020-08-28 21:50:25 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 447 ms / 1,000 ms |
コード長 | 3,063 bytes |
コンパイル時間 | 2,509 ms |
コンパイル使用メモリ | 205,020 KB |
実行使用メモリ | 11,648 KB |
最終ジャッジ日時 | 2024-04-26 14:44:15 |
合計ジャッジ時間 | 18,210 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,940 KB |
testcase_02 | AC | 2 ms
6,940 KB |
testcase_03 | AC | 110 ms
6,940 KB |
testcase_04 | AC | 268 ms
8,320 KB |
testcase_05 | AC | 10 ms
6,940 KB |
testcase_06 | AC | 15 ms
6,944 KB |
testcase_07 | AC | 126 ms
6,940 KB |
testcase_08 | AC | 188 ms
6,944 KB |
testcase_09 | AC | 109 ms
6,944 KB |
testcase_10 | AC | 28 ms
6,944 KB |
testcase_11 | AC | 85 ms
6,940 KB |
testcase_12 | AC | 81 ms
6,940 KB |
testcase_13 | AC | 29 ms
6,940 KB |
testcase_14 | AC | 25 ms
6,940 KB |
testcase_15 | AC | 20 ms
6,940 KB |
testcase_16 | AC | 170 ms
6,940 KB |
testcase_17 | AC | 81 ms
6,940 KB |
testcase_18 | AC | 182 ms
6,948 KB |
testcase_19 | AC | 46 ms
6,944 KB |
testcase_20 | AC | 321 ms
9,472 KB |
testcase_21 | AC | 206 ms
7,296 KB |
testcase_22 | AC | 108 ms
6,940 KB |
testcase_23 | AC | 151 ms
6,940 KB |
testcase_24 | AC | 206 ms
6,940 KB |
testcase_25 | AC | 33 ms
6,944 KB |
testcase_26 | AC | 235 ms
7,808 KB |
testcase_27 | AC | 189 ms
7,168 KB |
testcase_28 | AC | 445 ms
11,648 KB |
testcase_29 | AC | 419 ms
11,392 KB |
testcase_30 | AC | 427 ms
11,520 KB |
testcase_31 | AC | 429 ms
11,520 KB |
testcase_32 | AC | 435 ms
11,520 KB |
testcase_33 | AC | 442 ms
11,520 KB |
testcase_34 | AC | 426 ms
11,392 KB |
testcase_35 | AC | 433 ms
11,392 KB |
testcase_36 | AC | 426 ms
11,520 KB |
testcase_37 | AC | 444 ms
11,520 KB |
testcase_38 | AC | 441 ms
11,520 KB |
testcase_39 | AC | 419 ms
11,520 KB |
testcase_40 | AC | 424 ms
11,520 KB |
testcase_41 | AC | 418 ms
11,648 KB |
testcase_42 | AC | 431 ms
11,520 KB |
testcase_43 | AC | 415 ms
11,392 KB |
testcase_44 | AC | 427 ms
11,520 KB |
testcase_45 | AC | 436 ms
11,392 KB |
testcase_46 | AC | 447 ms
11,520 KB |
testcase_47 | AC | 430 ms
11,520 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; #define ALL(obj) (obj).begin(),(obj).end() #define SPEED cin.tie(0);ios::sync_with_stdio(false); template<class T> using PQ = priority_queue<T>; template<class T> using PQR = priority_queue<T,vector<T>,greater<T>>; constexpr long long MOD = (long long)1e9 + 7; constexpr long long MOD2 = 998244353; constexpr long long HIGHINF = (long long)1e18; constexpr long long LOWINF = (long long)1e15; constexpr long double PI = 3.1415926535897932384626433L; template <class T> vector<T> multivector(size_t N,T init){return vector<T>(N,init);} template <class... T> auto multivector(size_t N,T... t){return vector<decltype(multivector(t...))>(N,multivector(t...));} template <class T> void corner(bool flg, T hoge) {if (flg) {cout << hoge << endl; exit(0);}} template <class T, class U>ostream &operator<<(ostream &o, const map<T, U>&obj) {o << "{"; for (auto &x : obj) o << " {" << x.first << " : " << x.second << "}" << ","; o << " }"; return o;} template <class T>ostream &operator<<(ostream &o, const set<T>&obj) {o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;} template <class T>ostream &operator<<(ostream &o, const multiset<T>&obj) {o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;} template <class T>ostream &operator<<(ostream &o, const vector<T>&obj) {o << "{"; for (int i = 0; i < (int)obj.size(); ++i)o << (i > 0 ? ", " : "") << obj[i]; o << "}"; return o;} template <class T, class U>ostream &operator<<(ostream &o, const pair<T, U>&obj) {o << "{" << obj.first << ", " << obj.second << "}"; return o;} void print(void) {cout << endl;} template <class Head> void print(Head&& head) {cout << head;print();} template <class Head, class... Tail> void print(Head&& head, Tail&&... tail) {cout << head << " ";print(forward<Tail>(tail)...);} template <class T> void chmax(T& a, const T b){a=max(a,b);} template <class T> void chmin(T& a, const T b){a=min(a,b);} std::vector<std::string> split(const std::string &str, const char delemiter) {std::vector<std::string> res;std::stringstream ss(str);std::string buffer; while( std::getline(ss, buffer, delemiter) ) res.push_back(buffer); return res;} int msb(int x) {return x?31-__builtin_clz(x):-1;} void YN(bool flg) {cout << (flg ? "YES" : "NO") << endl;} void Yn(bool flg) {cout << (flg ? "Yes" : "No") << endl;} void yn(bool flg) {cout << (flg ? "yes" : "no") << endl;} int main() { int N,M; cin >> N >> M; auto A = multivector(N,M,0LL); for(int i=0;i<N;++i){ for(int j=0;j<M;++j){ cin >> A[i][j]; } } vector<ll> dp0(N+1,-LOWINF),dp1(N+1,-LOWINF); dp0[0]=0; for(int i=0;i<N;++i){ ll sum = accumulate(ALL(A[i]),0LL); chmax(dp0[i+1],dp0[i]); chmax(dp1[i+1],dp1[i]); chmax(dp1[i+1],dp0[i]+sum); chmax(dp0[i+1],dp1[i]-sum); } cout << max(dp0[N],dp1[N]) << endl; return 0; }