結果
問題 | No.1522 Unfairness |
ユーザー |
![]() |
提出日時 | 2021-05-28 20:37:48 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 55 ms / 2,000 ms |
コード長 | 751 bytes |
コンパイル時間 | 1,903 ms |
コンパイル使用メモリ | 175,160 KB |
実行使用メモリ | 38,528 KB |
最終ジャッジ日時 | 2024-11-19 06:08:06 |
合計ジャッジ時間 | 3,005 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
#include <bits/stdc++.h>using namespace std;const int INF = 1000000000;int main(){int N, M;cin >> N >> M;vector<int> A(N);for (int i = 0; i < N; i++){cin >> A[i];}sort(A.begin(), A.end(), greater<int>());vector<vector<int>> dp(N + 1, vector<int>(M + 1, -INF));dp[0][0] = 0;for (int i = 0; i < N; i++){for (int j = 0; j <= M; j++){if (dp[i][j] >= 0){dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);if (i < N - 1){int d = A[i] - A[i + 1];if (j + d <= M){dp[i + 2][j + d] = max(dp[i + 2][j + d], dp[i][j] + A[i]);}}}}}int ans = 0;for (int i = 0; i <= M; i++){ans = max(ans, dp[N][i]);}cout << ans << endl;}