結果

問題 No.818 Dinner time
コンテスト
ユーザー vjudge1
提出日時 2026-07-22 15:34:05
言語 C++14
(gcc 15.2.0 + boost 1.90.0)
コンパイル:
g++-15 -O2 -lm -std=c++14 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 2,083 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 450 ms
コンパイル使用メモリ 94,508 KB
実行使用メモリ 5,888 KB
最終ジャッジ日時 2026-07-22 15:34:09
合計ジャッジ時間 2,523 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 26 WA * 3
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <cstring>
#include <iostream>
#include <algorithm>
#include <functional>
#include <cstdio>
#include <queue>
#include <vector>

namespace std {
    class Read {
        public:
        template<typename T>
        inline Read operator >> (T & x) {
            T sum = 0; short opt = 1;
            char ch = getchar();
            while(!isdigit(ch)) opt = (ch == '-') ? -1 : 1, ch = getchar();
            while( isdigit(ch)) sum = (sum << 1) + (sum << 3) + (ch ^ 48), ch = getchar();
            x = sum * opt; return *this;
        }
    };
}
#define int long long
#define all(a) a.begin(), a.end()

using namespace std; Read fin;

using PII = pair<int, int> ;

signed main() {
    // freopen("remake.in", "r", stdin);
    // freopen("remake.out", "w", stdout);
    int n, m; fin >> n >> m;

    vector<int> a(n + 1), b(n + 1);

    for (int i = 1; i <= n; i ++ ) 
        fin >> a[i] >> b[i];

    if ([&]() -> bool {
        return a[1] == 0;
    }()) {
        int sum = 0;
        for (int i = 1; i <= n; i ++ )
            if (b[i] > 0) sum += b[i];
        cout << sum << endl;
    } else if([&]() -> bool {
        for (int i = 1; i <= n; i ++ )
            if (a[i] < 0 or b[i] < 0)
                return false;
        return true;
    }()) {
        int sum = 0;
        for (int i = 1; i <= n; i ++ )
            sum += a[i] * (m - 1) + max(a[i], b[i]);

        cout << sum << endl;
    } else {
        vector<int> ba(n + 2);
        for (int i = n; i; i -- ) {
            ba[i] = max(0ll, ba[i + 1] + max(a[i], b[i]));
        }
        // for (int i = 0; i <= n; i ++ )
        //     cout << ba[i] << " ";
        // cout << endl;
        int sum = 0, res = 0;
        for (int i = 0; i <= n; i ++ ) {
            if (a[i] < 0) {
                sum += max({a[i] * (m - 1) + b[i], b[i], a[i] * m});
            } else {
                sum += max(a[i] * m, a[i] * (m - 1) + b[i]);
            }
            // cout << sum << " ";
            res = max({res, sum + ba[i + 1], sum});
        }
        // cout << endl;

        cout << res << endl;
    }
}
0