結果
問題 | 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();}#endifconstexpr int mod = 1'000'000'007; //1e9+7(prime number)constexpr int INF = 1'000'000'000; //1e9constexpr ll LLINF = 2'000'000'000'000'000'000LL; //2e18constexpr 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;}