結果
問題 | No.286 Modulo Discount Store |
ユーザー | Ryuichiro Chiba |
提出日時 | 2021-02-26 21:42:45 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 15 ms / 2,000 ms |
コード長 | 4,249 bytes |
コンパイル時間 | 918 ms |
コンパイル使用メモリ | 105,236 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-10-02 14:18:19 |
合計ジャッジ時間 | 2,333 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,816 KB |
testcase_02 | AC | 4 ms
6,820 KB |
testcase_03 | AC | 1 ms
6,816 KB |
testcase_04 | AC | 2 ms
6,816 KB |
testcase_05 | AC | 2 ms
6,820 KB |
testcase_06 | AC | 7 ms
6,820 KB |
testcase_07 | AC | 2 ms
6,820 KB |
testcase_08 | AC | 1 ms
6,820 KB |
testcase_09 | AC | 2 ms
6,820 KB |
testcase_10 | AC | 3 ms
6,820 KB |
testcase_11 | AC | 1 ms
6,820 KB |
testcase_12 | AC | 2 ms
6,820 KB |
testcase_13 | AC | 4 ms
6,820 KB |
testcase_14 | AC | 2 ms
6,820 KB |
testcase_15 | AC | 1 ms
6,820 KB |
testcase_16 | AC | 1 ms
6,820 KB |
testcase_17 | AC | 15 ms
6,824 KB |
testcase_18 | AC | 2 ms
6,820 KB |
testcase_19 | AC | 1 ms
6,820 KB |
testcase_20 | AC | 2 ms
6,820 KB |
testcase_21 | AC | 2 ms
6,816 KB |
testcase_22 | AC | 2 ms
6,816 KB |
testcase_23 | AC | 5 ms
6,820 KB |
testcase_24 | AC | 2 ms
6,816 KB |
testcase_25 | AC | 2 ms
6,816 KB |
testcase_26 | AC | 1 ms
6,820 KB |
testcase_27 | AC | 3 ms
6,820 KB |
testcase_28 | AC | 7 ms
6,816 KB |
testcase_29 | AC | 2 ms
6,820 KB |
testcase_30 | AC | 1 ms
6,816 KB |
testcase_31 | AC | 2 ms
6,824 KB |
testcase_32 | AC | 2 ms
6,820 KB |
testcase_33 | AC | 1 ms
6,820 KB |
testcase_34 | AC | 2 ms
6,824 KB |
testcase_35 | AC | 2 ms
6,820 KB |
testcase_36 | AC | 1 ms
6,820 KB |
testcase_37 | AC | 2 ms
6,816 KB |
testcase_38 | AC | 2 ms
6,824 KB |
testcase_39 | AC | 7 ms
6,816 KB |
testcase_40 | AC | 1 ms
6,820 KB |
testcase_41 | AC | 1 ms
6,816 KB |
testcase_42 | AC | 1 ms
6,820 KB |
ソースコード
// {{{ #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <climits> #include <iostream> #include <iomanip> #include <algorithm> #include <vector> #include <list> #include <set> #include <unordered_set> #include <map> #include <unordered_map> #include <queue> #include <stack> #include <string> #include <numeric> #include <complex> #include <utility> #include <type_traits> #include <functional> using namespace std; #define fi first #define se second #define pb push_back #define mp make_pair #define FOR(i, a, b) for(ll i = static_cast<ll>(a); i < static_cast<ll>(b); ++i) #define FORR(i, a, b) for(ll i = static_cast<ll>(a); i >= static_cast<ll>(b); --i) #define REP(i, n) FOR(i, 0, n) #define REPR(i, n) FORR(i, n, 0) #define ALL(x) (x).begin(), (x).end() #define DBG(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl; using ll = long long; using ull = unsigned long long; using P = pair<int, int>; using LP = pair<ll, ll>; using IP = pair<int, P>; using LLP = pair<ll, LP>; const int dx[] = {1, -1, 0, 0}; const int dy[] = {0, 0, 1, -1}; constexpr int INF = 100000000; constexpr ll LINF = 10000000000000000ll; constexpr int MOD = static_cast<int>(1e9 + 7); constexpr double EPS = 1e-9; // {{{ popcount static int popcount(int x) { return __builtin_popcount(static_cast<unsigned int>(x)); } static int popcount(unsigned int x) { return __builtin_popcount(x); } static int popcount(long x) { return __builtin_popcountl(static_cast<unsigned long>(x)); } static int popcount(unsigned long x) { return __builtin_popcountl(x); } static int popcount(long long x) { return __builtin_popcountll(static_cast<unsigned long long>(x)); } static int popcount(unsigned long long x) { return __builtin_popcountll(x); } // }}} // template specialization of std::hash for std::pair namespace std { template<typename T, typename U> struct hash<pair<T, U> > { size_t operator()(const pair<T, U> &key) const noexcept { size_t h1 = hash<T>()(key.first); size_t h2 = hash<U>()(key.second); return h1 ^ (h2 << 1); } }; } // namespace std // print vector template<typename T> ostream &operator<<(ostream &os, const vector<T> &v) { size_t sz = v.size(); os << "["; for (size_t i = 0; i < sz-1; i++) { os << v[i] << ", "; } os << v[sz-1] << "]"; return os; } // print array (except char literal) template< typename T, int N, typename std::enable_if<!std::is_same<T, char>::value, std::nullptr_t>::type = nullptr> ostream &operator<<(ostream &os, const T (&v)[N]) { os << "["; for (size_t i = 0; i < N-1; i++) { os << v[i] << ", "; } os << v[N-1] << "]"; return os; } // print array template<typename T> void printArray(T *arr, size_t sz) { cerr << "["; for (size_t i = 0; i < sz-1; i++) { cerr << arr[i] << ","; } if (sz > 0) cerr << arr[sz-1]; cerr << "]" << endl; } // print pair template<typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &p) { os << "(" << p.first << ", " << p.se << ")"; return os; } static inline ll mod(ll x, ll m) { ll y = x % m; return (y >= 0 ? y : y+m); } struct Compare { //vector<ll> &x_, &y_; //Compare(vector<ll> &x, vector<ll> &y): x_(x), y_(y) {} //bool operator()(const P &lhs, const P &rhs) { // return x_[lhs.fi]+y_[lhs.se] < x_[rhs.fi]+y_[rhs.se]; //} bool operator()(const int x, const int y) { return x < y; } }; // print floating-point number // cout << fixed << setprecision(12) << // }}} int N; int m[15]; int dp[1<<15]; void solve() { REP (S, 1<<N) dp[S] = INF; dp[0] = 0; REP (S, 1<<N) { REP (i, N) { if (S & (1<<i)) continue; int s = 0; REP (j, N) { if (S & (1<<j)) s += m[j]; } int x = m[i] - (s % 1000); if (x < 0) x = 0; dp[S|(1<<i)] = min(dp[S|(1<<i)], dp[S] + x); } } cout << dp[(1<<N)-1] << endl; } int main() { cin.tie(0); ios::sync_with_stdio(false); cin >> N; REP (i, N) cin >> m[i]; solve(); return 0; } // vim:set foldmethod=marker: