結果
問題 |
No.733 分身並列コーディング
|
ユーザー |
|
提出日時 | 2023-12-14 21:34:03 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 184 ms / 1,500 ms |
コード長 | 3,790 bytes |
コンパイル時間 | 2,162 ms |
コンパイル使用メモリ | 200,980 KB |
最終ジャッジ日時 | 2025-02-18 10:57:52 |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 46 |
ソースコード
#include <bits/stdc++.h> // #if __has_include(<atcoder/all>) // #include <atcoder/all> // using namespace atcoder; // // using mint = modint; // // using mint = modint998244353; // // using mint = modint1000000007; // #endif #if __has_include(<my_debug_print.hpp>) #include <my_debug_print.hpp> #define debug(...) print_normal_for_debug(#__VA_ARGS__, __VA_ARGS__) #define debug_debug(...) print_format_for_debug(#__VA_ARGS__, __VA_ARGS__) #define debug_println(...) debug_println(__VA_ARGS__) #define debug_print(...) debug_print(__VA_ARGS__) #else #define debug(...) (static_cast<void>(0)) #define debug_debug(...) (static_cast<void>(0)) #define debug_println(...) (static_cast<void>(0)) #define debug_print(...) (static_cast<void>(0)) #endif using namespace std; using ll = long long; using ld = long double; constexpr char nl = '\n'; constexpr long long INF64 = 9223372036854775807; constexpr long long INF = 200'0000'0000'0000'0000; constexpr long double EPS = (long double)1e-13; #define rep(i, a, n) for(long long i = (long long)(a); i < (long long)(n); ++i) #define rrep(i, n, a) for(long long i = (long long)(n) - 1; (long long)(a) <= i; --i) #define all(a) std::begin(a), std::end(a) #define rall(a) std::rbegin(a), std::rend(a) #define Sort(a) sort(std::begin(a), std::end(a)) #define rsort(a) sort(std::rbegin(a), std::rend(a)) #define fi first #define se second template <typename T> void my_print(const T &arg) { std::cout << arg; } template <typename T, typename... U> void my_print(const T &arg, const U&... args) { std::cout << arg; my_print(args...); } long long solve1( const long long& m, const long long& n, const vector<long long>& A ) { debug(n, m); debug(A); long long T = m; long long N = n; vector<long long> t = A; vector<vector<long long>> dp; dp.assign(N + 1, vector<long long>((1 << N) + 1, INF)); dp[0][0] = 0; for (long long k = 0; k < N; ++k) { for (long long bit = 0; bit < (1 << N); ++bit) { if (dp[k][bit] <= T) dp[k + 1][bit] = 0; for (long long i = 0; i < N; ++i) { if (bit & (1 << i)) continue; long long nbit = bit | (1 << i); dp[k][nbit] = min(dp[k][nbit], dp[k][bit] + t[i]); if (dp[k][nbit] + t[i] <= T) dp[k+1][nbit] = 0; } } } long long res = N; for (long long k = 0; k < N; ++k) { if (dp[k][(1 << N) - 1] == 0) { res = min(res, k); } } debug(res); my_print(res, nl); return res; } long long solve2( const long long& T, const long long& N, const vector<long long>& A ) { debug(N, T); debug(A); return 0LL; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); std::cout << std::fixed << std::setprecision(15); { long long times = 1LL; { const char *file = "./_input.txt"; FILE *fp; fp = fopen(file, "r"); if (fp != NULL) { times = 3LL; // サンプルの数に合わして繰り返す回数を決めることにする。 fclose(fp); } } for (long long _index = 1LL; _index <= times; ++_index) { debug_println("--------------------------------", _index, "---------------------------------", '\n'); long long T, N; cin >> T >> N; vector<long long> A(N, 0LL); rep (i1, 0, N) { cin >> A[i1]; } solve1(T, N, A); // solve2(T, N, A); debug_println("------------------------------------------------------------------", '\n'); } } return 0; }