結果
問題 |
No.286 Modulo Discount Store
|
ユーザー |
![]() |
提出日時 | 2021-02-04 14:11:10 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 5 ms / 2,000 ms |
コード長 | 1,270 bytes |
コンパイル時間 | 3,188 ms |
コンパイル使用メモリ | 105,576 KB |
最終ジャッジ日時 | 2025-01-18 11:15:33 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 40 |
ソースコード
#pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include<iostream> #include<cstdint> #include<cstddef> #include<vector> //#include<atcoder/all> //using namespace atcoder; using namespace std; using i32 = int_fast32_t; using i64 = int_fast64_t; using usize = size_t; using u32 = uint_fast32_t; using u64 = uint_fast64_t; using i128 = __int128_t; using u128 = __uint128_t; using ld = long double; template<typename T> using vec = vector<T>; #define rep(i, n) for (i64 i = 0; i < (i64)(n); ++i) #define all(a) (a).begin(),(a).end() #define rall(a) (a).rbegin(),(a).rend() #define len(hoge) (i64)((hoge).size()) using P = pair<i64,i64>; template<class T, class S> ostream &operator<<(ostream &os, const pair<T,S> &p){ os << p.first << " " << p.second; return os; } int main(){ ios::sync_with_stdio(false); std::cin.tie(nullptr); i64 n; cin >> n; vec<i64> a(n); rep(i,n)cin >> a[i]; vec<i64> dp(1 <<n,1e18); dp[0] = 0; rep(Set,1 << n){ i64 sum = 0; rep(bit,n){ if(Set&(1 << bit))sum += a[bit]; } rep(bit,n){ if(!(Set & (1 << bit))){ dp[Set | (1 << bit)] = min(dp[Set | (1 << bit)], dp[Set] + max<i64>(a[bit] - sum % 1000,0)); } } } cout << dp.back() << endl; // for(auto v:dp)cout << v << " "; }