結果
問題 |
No.286 Modulo Discount Store
|
ユーザー |
![]() |
提出日時 | 2018-09-07 00:21:32 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 5 ms / 2,000 ms |
コード長 | 1,092 bytes |
コンパイル時間 | 1,304 ms |
コンパイル使用メモリ | 158,652 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-11-24 12:53:32 |
合計ジャッジ時間 | 2,356 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 40 |
ソースコード
#include <bits/stdc++.h> using namespace std; //#define int long long #define INF 1e9 #define LINF 1e18 const int MOD = 1e9 + 7; const int dy[]={0, 0, 1, -1}; const int dx[]={1, -1, 0, 0}; typedef pair<int, int> P; typedef pair<P, int> Pi; typedef pair<P, P> PP; template <class T> void chmin(T& a, const T& b) { a = min(a, b); } template <class T> void chmax(T& a, const T& b) { a = max(a, b); } int N, M[15]; int dp[1 << 15], sum[1 << 15]; signed main() { cin.tie(0); ios::sync_with_stdio(false); cin >> N; for(int i = 0; i < N; ++i) cin >> M[i]; for(int mask = 0; mask < (1 << N); ++mask) { dp[mask] = INF; for(int i = 0; i < N; ++i) { if(mask & (1 << i)) sum[mask] += M[i]; } } dp[0] = 0; for(int mask = 0; mask < (1 << N); ++mask) { for(int i = 0; i < N; ++i) { if(mask & (1 << i)) continue; int add = M[i] - sum[mask] % 1000; chmax(add, 0); chmin(dp[mask | (1 << i)], dp[mask] + add); } } cout << dp[(1 << N) - 1] << endl; return 0; }