結果

問題 No.818 Dinner time
ユーザー CuriousFairy315
提出日時 2019-04-18 13:52:42
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,246 bytes
コンパイル時間 471 ms
コンパイル使用メモリ 66,056 KB
実行使用メモリ 13,756 KB
最終ジャッジ日時 2024-09-22 09:12:12
合計ジャッジ時間 4,409 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 13 TLE * 1 -- * 15
権限があれば一括ダウンロードができます

ソースコード

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