結果
| 問題 |
No.3302 Sense Battle
|
| コンテスト | |
| ユーザー |
回転
|
| 提出日時 | 2025-10-05 19:06:12 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 443 ms / 2,000 ms |
| コード長 | 819 bytes |
| コンパイル時間 | 1,741 ms |
| コンパイル使用メモリ | 193,972 KB |
| 実行使用メモリ | 203,044 KB |
| 最終ジャッジ日時 | 2025-10-05 19:06:22 |
| 合計ジャッジ時間 | 8,954 ms |
|
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| other | AC * 18 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e18;
int N,a,b;
int A[5050];
int B[5050];
int memo[5050][5050];
int f(int n,int atk){
if(memo[n][atk] != -1)return memo[n][atk];
if(n == N){
return atk == 0 ? 0:-INF;
}
int ret;
// 攻撃しない
ret = f(n+1,atk) + A[n] * atk;
// 攻撃する
if(atk > 0)ret = max(ret, f(n+1,atk-1) + B[n]);
return memo[n][atk] = ret;
}
signed main(){
for (int i = 0;i < 5050;i++)
{
for (int j = 0;j < 5050;j++)
{
memo[i][j] = -1;
}
}
cin >> N;
for (int i = 0;i < N;i++)
{
cin >> A[i] >> B[i];
}
int ans = 0;
for(int i = 1;i <= N;i++)
{
ans = max(ans, f(0,i));
}
cout << ans << endl;
return 0;
}
回転