結果

問題 No.1522 Unfairness
ユーザー goodbaton
提出日時 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);
      |                               ~~~~~^~~~~~~~~~~~~

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0