#include #include #include #include #include #define mod 1000000007LL #define MAX 1'000'000LL using namespace std; using ll = long long; ll n; ll dp[2001][101]; // dp[i][j] 일 때, i번째 game에서 hp가 j일 때의 점수 ll uk; pair games[2001]; int main(){ cin >> n >> uk; ll result = 0; for(int i = 1; i <= n; i++) cin >> games[i].first; // score for(int i = 1; i <= n; i++){ cin >> games[i].second; // health } for(int i = 0; i <= n; i++){ for(int j = 0; j < 101; j++){ dp[i][j] = -1; } } // // for(int i = 1; i < n; i++){ // for(int j = i+1; j <= n; j++){ // for(int k = 1; k < 101; k++){ // // dp[j][min(k+(uk* (j - i)), 100LL)] = max(dp[i][k], dp[j][min(k+(uk* (j - i)), 100LL)]); // if(!dp[i][k] || k+(uk* (j - i)) - games[j].second < 0) continue; // ll ch = min(100LL, k+(uk* (j - i)) - games[j].second); // dp[j][ch] = max(dp[i][k] + games[j].first, dp[j][ch]); // result= max(dp[j][ch], result); // } // } // } dp[0][100] = 0; for(int i = 0; i < n; i++){ for(int j = 0; j <= 100; j++){ if(dp[i][j] == -1) continue; dp[i+1][min(j+uk, 100LL)] = max(dp[i+1][min(j+uk, 100LL)], dp[i][j]); ll ch = min(j+uk-games[i+1].second, 100LL); if(ch > 0) dp[i+1][ch] = max(dp[i+1][ch], dp[i][j] + games[i+1].first); // cout << dp[i+1][ch] << " " << ch << " " << i+1 << "\n"; result = max({dp[i+1][ch], result, dp[i+1][min(j+uk, 100LL)]}); } } cout << result; return 0; } /* 2 0 1 2 99 1 1 5 1 100 */

제출 #117043

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력: