結果
問題 | No.1522 Unfairness |
ユーザー | goodbaton |
提出日時 | 2021-05-28 21:42:50 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 57 ms / 2,000 ms |
コード長 | 2,626 bytes |
コンパイル時間 | 1,274 ms |
コンパイル使用メモリ | 120,428 KB |
実行使用メモリ | 97,556 KB |
最終ジャッジ日時 | 2023-08-12 07:27:14 |
合計ジャッジ時間 | 3,041 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge12 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,380 KB |
testcase_01 | AC | 2 ms
4,376 KB |
testcase_02 | AC | 2 ms
4,380 KB |
testcase_03 | AC | 17 ms
33,644 KB |
testcase_04 | AC | 9 ms
26,888 KB |
testcase_05 | AC | 10 ms
37,160 KB |
testcase_06 | AC | 19 ms
74,540 KB |
testcase_07 | AC | 23 ms
42,024 KB |
testcase_08 | AC | 33 ms
82,776 KB |
testcase_09 | AC | 10 ms
37,060 KB |
testcase_10 | AC | 20 ms
66,180 KB |
testcase_11 | AC | 7 ms
22,464 KB |
testcase_12 | AC | 12 ms
25,340 KB |
testcase_13 | AC | 32 ms
64,452 KB |
testcase_14 | AC | 5 ms
12,616 KB |
testcase_15 | AC | 56 ms
97,344 KB |
testcase_16 | AC | 57 ms
97,340 KB |
testcase_17 | AC | 57 ms
97,556 KB |
testcase_18 | AC | 55 ms
97,556 KB |
testcase_19 | AC | 56 ms
97,356 KB |
testcase_20 | AC | 56 ms
97,416 KB |
testcase_21 | AC | 1 ms
4,376 KB |
testcase_22 | AC | 1 ms
4,380 KB |
testcase_23 | AC | 2 ms
4,380 KB |
testcase_24 | AC | 2 ms
4,380 KB |
testcase_25 | AC | 1 ms
4,380 KB |
testcase_26 | AC | 2 ms
4,376 KB |
testcase_27 | AC | 1 ms
4,380 KB |
testcase_28 | AC | 1 ms
4,380 KB |
testcase_29 | AC | 3 ms
4,380 KB |
ソースコード
#include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <bitset> #include <complex> #include <iostream> #include <map> #include <numeric> #include <queue> #include <set> #include <stack> #include <string> #include <unordered_map> #include <unordered_set> #include <vector> #include <cassert> #include <functional> using ll = long long; using namespace std; template<typename A, typename B> bool chmin(A &a, const B b) { if (a <= b) return false; a = b; return true; } template<typename A, typename B> bool chmax(A &a, const B b) { if (a >= b) return false; a = b; return true; } #ifndef LOCAL #define debug(...) ; #else #define debug(...) cerr << __LINE__ << " : " << #__VA_ARGS__ << " = " << _tostr(__VA_ARGS__) << endl; template<typename T> ostream &operator<<(ostream &out, const vector<T> &v); template<typename T1, typename T2> ostream &operator<<(ostream &out, const pair<T1, T2> &p) { out << "{" << p.first << ", " << p.second << "}"; return out; } template<typename T> ostream &operator<<(ostream &out, const vector<T> &v) { out << '{'; for (const T &item : v) out << item << ", "; out << "\b\b}"; return out; } void _tostr_rec(ostringstream &oss) { oss << "\b\b \b"; } template<typename Head, typename... Tail> void _tostr_rec(ostringstream &oss, Head &&head, Tail &&...tail) { oss << head << ", "; _tostr_rec(oss, forward<Tail>(tail)...); } template<typename... T> string _tostr(T &&...args) { ostringstream oss; int size = sizeof...(args); if (size > 1) oss << "{"; _tostr_rec(oss, forward<T>(args)...); if (size > 1) oss << "}"; return oss.str(); } #endif constexpr int mod = 1'000'000'007; //1e9+7(prime number) constexpr int INF = 1'000'000'000; //1e9 constexpr ll LLINF = 2'000'000'000'000'000'000LL; //2e18 constexpr int SIZE = 4010; int dp[SIZE][SIZE][2]; int main() { int N, M; int A[SIZE]; scanf("%d%d", &N, &M); for (int i = 0; i < N; i++) scanf("%d", A + i); sort(A, A + N, greater<int>()); for (int i = 0; i <= N; i++) { for (int j = 0; j <= N; j++) { dp[i][j][0] = dp[i][j][1] = -INF; } } dp[0][0][0] = 0; for (int i = 0; i < N; i++) { for (int j = M; j >= 0; j--) { int d = A[i] - A[i + 1]; int tmp = dp[i][j][0]; chmax(dp[i][j][0], dp[i][j][1]); chmax(dp[i][j][1], tmp + A[i]); chmax(dp[i + 1][j][0], dp[i][j][0]); if (j + d <= M) chmax(dp[i + 1][j + d][1], dp[i][j][1]); } } int ans = -INF; for (int i = 0; i <= M; i++) { chmax(ans, dp[N - 1][i][0]); } cout << ans << endl; return 0; }