結果

問題 No.1375 Divide and Update
ユーザー leaf_1415
提出日時 2019-02-27 00:32:55
言語 C++11(廃止可能性あり)
(gcc 13.3.0)
結果
AC  
実行時間 55 ms / 2,000 ms
コード長 1,017 bytes
コンパイル時間 1,172 ms
コンパイル使用メモリ 54,908 KB
実行使用メモリ 17,480 KB
最終ジャッジ日時 2024-07-20 03:32:09
合計ジャッジ時間 4,525 ms
ジャッジサーバーID
(参考情報)
judge5 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff #

#include <iostream>
#define llint long long
#define inf 1e18

using namespace std;

llint n, x, y;
llint a[200005], b[200005], c[200005];
llint B[200005], C[200005];
llint minB[200005], minC[200005];
llint maxL[200005], maxR[200005];

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> x >> y;
	for(int i = 1; i <= n; i++) cin >> a[i];
	
	llint sum = 0;
	for(int i = 1; i <= n; i++) sum += a[i];
	for(int i = 1; i <= n; i++) b[i] = x - a[i], c[i] = y - a[i];
	
	for(int i = 1; i <= n; i++) B[i] = B[i-1] + b[i];
	for(int i = n; i >= 1; i--) C[i] = C[i+1] + c[i];
	
	minB[0] = 0;
	for(int i = 1; i <= n; i++) minB[i] = min(minB[i-1], B[i]);
	minC[n+1] = 0;
	for(int i = n; i >= 1; i--) minC[i] = min(minC[i+1], C[i]);
	
	maxL[0] = maxR[n+1] = -inf;
	for(int i = 1; i < n; i++) maxL[i] = max(maxL[i-1], B[i]-minB[i-1]);
	for(int i = n; i > 1; i--) maxR[i] = max(maxR[i+1], C[i]-minC[i+1]);
	
	for(int i = 2; i < n; i++){
		cout << sum + maxL[i-1] + maxR[i+1] << "\n";
	}
	flush(cout);
	
	return 0;
}
0