結果
問題 |
No.286 Modulo Discount Store
|
ユーザー |
![]() |
提出日時 | 2018-06-21 01:29:13 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 6 ms / 2,000 ms |
コード長 | 2,123 bytes |
コンパイル時間 | 4,838 ms |
コンパイル使用メモリ | 169,580 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-30 17:32:42 |
合計ジャッジ時間 | 3,160 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 40 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define ll long long #define vvi vector<vector<int>> #define vec vector #define pq priority_queue #define all(v) (v).begin(), (v).end() #define uniqueV(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end()); #define rep(i, n) for (int (i) = (0); (i) < (n); ++(i)) #define repp(i, m, n) for (int (i) = (m); (i) < (n); ++(i)) #define dbg(x) cerr << #x << ": " << x << endl; #define dbg2(x, y) cerr<<"("<<#x<<", "<<#y<<") = "<<"("<<x<<", "<<y<<")"<<endl; #define dbg3(x, y, z) cerr<<"("<<#x<<", "<<#y<<", "<<#z<<") = "<<"("<<x<<", "<<y<<", "<<z<<")"<<endl; #define dbgB(value, size) cerr<<#value<<": "<<bitset<size>(value) << endl; #define line() cerr << "---------------" << endl; const int dx[] = {1, -1, 0, 0}; const int dy[] = {0, 0, -1, 1}; const double PI = 3.14159265358979323846; template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; } template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; } template<typename T> void printA(vector<T> &printArray, char between = ' ') { int paSize = printArray.size(); for (int i = 0; i < paSize; i++) { cerr << printArray[i] << between;} if (between != '\n') {cerr << endl;} } // ------------------------------------------------------------------------------------------ int N; int M[20]; int dp[1<<20]; void guchoku() { sort(M, M+N); int ans = 1e8; do { int teikaSum = 0; int cand = 0; rep (i, N) { int price = max(0, M[i] - teikaSum % 1000); cand += price; teikaSum += M[i]; } chmin(ans, cand); } while (next_permutation(M, M+N)); cout << ans << endl; } int main() { cin >> N; rep (i, N) { cin >> M[i]; } rep (i, 1<<N) dp[i] = 1<<20; dp[0] = 0; for (int mask = 0; mask < (1<<N)-1; mask++) { int tot = 0; rep (i, N) if (mask & (1<<i)) tot += M[i]; tot %= 1000; rep (i, N) if ((mask&(1<<i))==0) dp[mask | (1<<i)] = min(dp[mask | (1<<i)], dp[mask]+max(0, M[i]-tot)); } cout << dp[(1<<N)-1] << endl; return 0; }