結果
問題 |
No.3302 Sense Battle
|
ユーザー |
![]() |
提出日時 | 2025-10-09 16:27:41 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 48 ms / 2,000 ms |
コード長 | 1,043 bytes |
コンパイル時間 | 3,494 ms |
コンパイル使用メモリ | 279,228 KB |
実行使用メモリ | 7,716 KB |
最終ジャッジ日時 | 2025-10-09 16:27:47 |
合計ジャッジ時間 | 5,430 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 18 |
ソースコード
#include <bits/stdc++.h> //#include <atcoder/modint> using namespace std; //using namespace atcoder; using ll = long long; //using mint = modint998244353; int main(){ cin.tie(nullptr); ios_base::sync_with_stdio(false); /* 後ろから見ていく。 1種類目: 後ろの攻撃回数*Aを足す。 2種類目: Bを足す。 dp(i, j) = 後ろから見ていってi番目までにj回攻撃している時の最大値 */ ll N; cin >> N; vector<ll> A(N), B(N); for (int i=0; i<N; i++) cin >> A[i] >> B[i]; const ll inf = -1e18; vector<ll> dp(N+1, inf); dp[0] = 0; for (int i=N-1; i>=0; i--){ vector<ll> pd(N+1, inf); for (int j=0; j<=N; j++){ if (dp[j] != inf){ if (j+1<=N) pd[j+1] = max(pd[j+1], dp[j]+B[i]); pd[j] = max(pd[j], dp[j]+A[i]*j); } } swap(dp, pd); } ll ans=inf; for (int i=0; i<=N; i++) ans = max(ans, dp[i]); cout << ans << endl; return 0; }