#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 if(games[i].second - uk > 100) continue; dp[i][min(100LL, 100LL - games[i].second + uk)] = games[i].first; result = max(games[i].first, result); } // // 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); // } // } // } for(int i = 1; i < n; i++){ for(int j = 0; j <= 100; j++){ dp[i+1][min(j+uk, 100LL)] = max(dp[i+1][min(j+uk, 100LL)], dp[i][j]); if(dp[i][j] <= 0 || j+uk-games[i+1].second < 0) continue; ll ch = min(j+uk-games[i+1].second, 100LL); dp[i+1][ch] = max(dp[i+1][ch], dp[i][j] + games[i+1].first); result = max(dp[i+1][ch], result); } } cout << result; return 0; } /* 2 0 1 2 99 1 1 5 1 100 */

제출 #116833

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력: