結果
問題 |
No.1375 Divide and Update
|
ユーザー |
![]() |
提出日時 | 2021-02-07 19:18:06 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 55 ms / 2,000 ms |
コード長 | 1,398 bytes |
コンパイル時間 | 776 ms |
コンパイル使用メモリ | 95,928 KB |
実行使用メモリ | 13,796 KB |
最終ジャッジ日時 | 2024-07-04 12:16:02 |
合計ジャッジ時間 | 4,143 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 19 |
ソースコード
/* -*- coding: utf-8 -*- * * 1375.cc: No.1375 Divide and Update - yukicoder */ #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<string> #include<vector> #include<map> #include<set> #include<stack> #include<list> #include<queue> #include<deque> #include<algorithm> #include<numeric> #include<utility> #include<complex> #include<functional> using namespace std; /* constant */ const int MAX_N = 200000; const long long LINF = 1LL << 62; /* typedef */ typedef long long ll; /* global variables */ int as[MAX_N]; ll dpx[MAX_N + 1][3], dpy[MAX_N + 1][3]; /* subroutines */ /* main */ int main() { int n, x, y; scanf("%d%d%d", &n, &x, &y); for (int i = 0; i < n; i++) scanf("%d", as + i); dpx[0][0] = 0, dpx[0][1] = dpx[0][2] = -LINF; for (int i = 0; i < n; i++) { dpx[i + 1][0] = dpx[i][0] + as[i]; dpx[i + 1][1] = max(dpx[i][0], dpx[i][1]) + x; dpx[i + 1][2] = max(dpx[i][1], dpx[i][2]) + as[i]; } dpy[n][0] = 0, dpy[n][1] = dpy[n][2] = -LINF; for (int i = n - 1; i >= 0; i--) { dpy[i][0] = dpy[i + 1][0] + as[i]; dpy[i][1] = max(dpy[i + 1][0], dpy[i + 1][1]) + y; dpy[i][2] = max(dpy[i + 1][1], dpy[i + 1][2]) + as[i]; } for (int i = 1; i < n - 1; i++) { ll sum = max(dpx[i][1], dpx[i][2]) + as[i] + max(dpy[i + 1][1], dpy[i + 1][2]); printf("%lld\n", sum); } return 0; }