結果

問題 No.818 Dinner time
ユーザー CuriousFairy315CuriousFairy315
提出日時 2019-04-18 13:52:42
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 1,246 bytes
コンパイル時間 1,205 ms
コンパイル使用メモリ 65,044 KB
実行使用メモリ 9,260 KB
最終ジャッジ日時 2023-10-22 08:11:34
合計ジャッジ時間 5,243 ms
ジャッジサーバーID
（参考情報） 		judge10 / judge9
このコードへのチャレンジ（β）

テストケース

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

ソースコード

diff # 

#include<iostream>
#include<cstdint>
using namespace std; // 575

const int64_t INF = 4611686018427387903; // 10^62-1、使わない辺とかに用いる
const int MAX = 100001; // 配列長
int main() {
	int64_t N, M, A, B;
	cin >> N >> M;
	static int64_t cumsum[MAX], cumsum2[MAX];
	cumsum[0] = cumsum2[0] = 0;
	for (int i = 1;i <= N;++ i) {
		cin >> A >> B;
		cumsum[i] = cumsum[i - 1] + max(max(A, B) + (M - 1) * A, B);
		cumsum2[i] = cumsum2[i - 1] + max(A, B);
	}
	int64_t ans = -INF;
	for (int i = 1;i <= N;++ i) { // i: 毎日選ぶ範囲 (0, i]が毎日選ばれる
		for (int j = i;j <= N;++ j) { // j: 1日選ぶ範囲 (i, j]が1日だけ選ばれる
			ans = max(ans, cumsum[i] + (cumsum2[j] - cumsum2[i]));
		}
	}
	cout << ans << endl;
	return 0;
}
/*
31536000のコメント解説欄
ここテンプレで用意してるから、A問題とかだとこの先空欄の危険あり
また、コンテスト後に https://31536000.hatenablog.com/ で解説していると思うので、良かったら読んでねー

一応、O(N^2)の確認を
毎日/1日/選ばない、の3通りがこの順に出るので、仕切りを2か所決め打つ
この時のコストは累積和からO(1)で計算できるので、それを用いる
*/
0