結果
問題 | No.1522 Unfairness |
ユーザー |
![]() |
提出日時 | 2021-05-28 21:42:50 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 52 ms / 2,000 ms |
コード長 | 2,626 bytes |
コンパイル時間 | 1,163 ms |
コンパイル使用メモリ | 117,992 KB |
最終ジャッジ日時 | 2025-01-21 19:57:11 |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:94:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 94 | scanf("%d%d", &N, &M); | ~~~~~^~~~~~~~~~~~~~~~ main.cpp:96:36: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 96 | for (int i = 0; i < N; i++) scanf("%d", A + i); | ~~~~~^~~~~~~~~~~~~
ソースコード
#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; }