結果
問題 | No.3014 岩井満足性問題 |
ユーザー |
|
提出日時 | 2025-01-03 21:42:53 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 132 ms / 3,000 ms |
コード長 | 7,054 bytes |
コンパイル時間 | 7,697 ms |
コンパイル使用メモリ | 326,144 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2025-01-25 21:56:51 |
合計ジャッジ時間 | 7,333 ms |
ジャッジサーバーID (参考情報) |
judge10 / judge7 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 18 |
ソースコード
#ifndef MAIN #define MAIN #include __FILE__ string solve(int n, int d, int k, vector<int> a, vector<int> c) { assert(n >= d && d >= 1 && k >= 1 && n <= 500 && k <= 1000 && *min_element(all(a)) >= -1000000000 && *max_element(all(a)) <= 1000000000 && *min_element(all(c)) >= 0 && *max_element(all(c)) <= 1000000000); vector<vector<int>> dp(d + 1, vector<int>(k + 1, -inf)); dp[0][0] = 0; rep(i, n) { repr(j, d) { repr(l, k + 1) { if (dp[j][l] != -inf) if (dp[j + 1][min(k, l + c[i])] < dp[j][l] + a[i]) dp[j + 1][min(k, l + c[i])] = dp[j][l] + a[i]; } } } int ans = dp[d][k]; if (ans == -inf) { return "No"; } return to_string(ans); } void _main() { cint(n, d, k); cvec(n, a); cvec(n, c); cout << solve(n, d, k, a, c) << endl; } #else #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef vector<string> strvec; constexpr ll mod10 = 1000000007; constexpr ll mod9 = 998244353; #define int ll #define double ld #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define repf(i, s, n) for (int i = s; i < (int)(n); i++) #define repr(i, n) for (int i = n - 1; i >= 0; i--) #define reprt(i, e, n) for (int i = n - 1; i >= e; i--) #define rep2(i, j, n, m) rep(i, n) rep(j, m) template <class... Args> void __y_input(Args &...arg) { (cin >> ... >> arg); } template <class... Args> void __y_input_vec_1(int p, Args &...args) { (cin >> ... >> args[p]); } template <class... Args> void __y_input_vec_2(int p, int q, Args &...args) { (cin >> ... >> args[p][q]); } template <class Arg> void __y_input_vec_resize(int size, Arg &arg) { arg.resize(size); } template <class Arg_t> void __y_input_vec_resize_2(int n, int m, vector<Arg_t> &arg) { arg.assign(n, Arg_t(m)); } template <class... Args> void __y_input_vec(int n, Args &...args) { (__y_input_vec_resize(n, args), ...); rep(i, n) { (__y_input_vec_1(i, args), ...); } } template <class... Args> void __y_input_vec2(int n, int m, Args &...args) { (__y_input_vec_resize_2(n, m, args), ...); rep2(i, j, n, m) { (__y_input_vec_2(i, j, args), ...); } } template <class T, class... Args> void SyncSort(vector<T> &vec, vector<Args> &...args) { vector<pair<T, tuple<Args...>>> z; rep(i, vec.size()) { z.push_back({vec[i], make_tuple(args.at(i)...)}); } sort(z.begin(), z.end()); rep(i, vec.size()) { vec[i] = z[i].first; tie(args[i]...) = z[i].second; } } #define cint(...) \ int __VA_ARGS__; \ __y_input(__VA_ARGS__) #define cdbl(...) \ double __VA_ARGS__; \ __y_input(__VA_ARGS__) #define cstr(...) \ string __VA_ARGS__; \ __y_input(__VA_ARGS__) #define cit(t, ...) \ t __VA_ARGS__; \ __y_input(__VA_ARGS__) #define cvec(n, ...) \ vector<int> __VA_ARGS__; \ __y_input_vec(n, __VA_ARGS__) #define cvect(t, n, ...) \ vector<t> __VA_ARGS__; \ __y_input_vec(n, __VA_ARGS__) #define cvec2(n, m, ...) \ vector<vector<int>> __VA_ARGS__; \ __y_input_vec2(n, m, __VA_ARGS__) #define cvec2t(t, n, m, ...) \ vector<vector<t>> __VA_ARGS__; \ __y_input_vec2(n, m, __VA_ARGS__) #define cvecs(n, ...) cvect(string, n, __VA_ARGS__) #define yn(bl) (bl ? "Yes" : "No") #define all(v) v.begin(), v.end() template <typename T> using vec2 = vector<vector<T>>; template <typename T> using vec3 = vector<vector<vector<T>>>; template <typename T> constexpr T limit() { return numeric_limits<long long>::max(); } constexpr ll inf = limit<ll>() / 100; template <typename T> constexpr T limit(T _) { return numeric_limits<long long>::max(); } typedef array<int, 2> xy; typedef array<int, 3> xyz; template <typename T> inline void sort(T &vec) { return sort(vec.begin(), vec.end()); } template <typename T> inline void rsort(T &vec) { return sort(vec.rbegin(), vec.rend()); } template <typename T> inline vector<vector<T>> rotate90(const vector<vector<T>> &vec) { vector<vector<T>> res(vec[0].size(), vector<T>(vec.size())); rep(i, vec.size()) { rep(j, vec[0].size()) { res[j][vec.size() - i - 1] = vec[i][j]; } } return res; } template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) { for (T val : vec) { os << val << ' '; } return os; } template <typename T> vector<T> &operator+=(vector<T> &vec, const T &val) { vec.push_back(val); return vec; } template <typename T> vector<T> &operator+=(vector<T> &vec, const vector<T> &val) { vec.insert(vec.end(), val.begin(), val.end()); return vec; } template <typename T> vector<T> &operator+=(vector<T> &vec, const initializer_list<T> &val) { vec.insert(vec.end(), val.begin(), val.end()); return vec; } template <typename T> vector<vector<T>> operator*(vector<T> &vec, int val) { return vector<vector<T>>(val, vec); } void _main(); signed main() { cin.tie(0); ios_base::sync_with_stdio(false); cout << fixed << setprecision(15); _main(); return 0; } // Libraries Begin class Debugger { ostream &os; public: Debugger(ostream &os) : os{os} {} template <typename T> Debugger &operator,(T val) { os << val << ' '; return *this; } Debugger &operator,(char val) { os << val; return *this; } template <typename T> Debugger &operator,(vector<T> vec) { *this, '['; rep(i, vec.size()) { *this, vec[i], ' ', ", "[i + 1 == vec.size()]; } *this, "]\n"; return *this; } template <typename T, typename U> Debugger &operator,(map<T, U> mp) { *this, "{\n"; for (auto [key, val] : mp) { *this, '\t', key, ": ", val, '\n'; } *this, "}\n"; return *this; } template <typename T, typename U> Debugger &operator,(pair<T, U> p) { *this, '(', p.first, ", ", p.second, ')'; return *this; } }; Debugger debugger(cerr); map<int, int> prime_factorize(int n) { map<int, int> res; for (int i = 2; i * i <= n; i += 1 + i > 2) { while (n % i == 0) { res[i]++; n /= i; } } if (n != 1) { res[n]++; } return res; } // Libraries End // Defines template <typename... T> common_type_t<T...> __yc_max(T... args) { return max(initializer_list<common_type_t<T...>>{args...}); } template <typename... T> common_type_t<T...> __yc_min(T... args) { return min(initializer_list<common_type_t<T...>>{args...}); } template <typename T> vector<T> iota(size_t n, T start = 0) { vector<T> res(n); iota(all(res), start); return res; } #define max(...) __yc_max(__VA_ARGS__) #define min(...) __yc_min(__VA_ARGS__) // Defines End #endif // 自分ここまでよくこのコード書いた! // __ ====^^==== //===\\ ======= ||=====\\ ||====== ||=====\| + // //\\ || // \\ // \\ || \| || || || + // // \\ || || || || || || ||====== ||=====// + // //====\\ || \\ // \\ // || /| || || \\\ + // // \\ || \===// \=====// ||=====// ||====== || \\\ +