結果
問題 |
No.286 Modulo Discount Store
|
ユーザー |
|
提出日時 | 2016-02-13 20:29:55 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 7 ms / 2,000 ms |
コード長 | 1,825 bytes |
コンパイル時間 | 559 ms |
コンパイル使用メモリ | 68,676 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-09-22 06:16:24 |
合計ジャッジ時間 | 1,835 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 40 |
ソースコード
#define _CRT_SECURE_NO_WARNINGS #define _USE_MATH_DEFINES #include <iostream> #include <cstring> #include <algorithm> #include <limits.h> #include <cmath> #include <cstdio> #include <vector> #include <set> #include <string> #include <cstdlib> #define REP(i,a,b) for(i=a;i<b;i++) #define rep(i,n) REP(i,0,n) using namespace std; typedef long long ll; typedef unsigned long long ull; typedef long double ld; /* pow(x,n)はx^nを返すよ! */ ull pow(ull x,ull n) { ull res = 1; while(n > 0) { if(n&1) res = res * x; x = x * x; n >>= 1; } return res; } template<typename T> T combi(T n,T r) { T i,j; T rep = 1; if(r > n/2) r = n-r; rep(i,r) rep *= n-i; rep(i,r) rep /= r-i; return rep; } // 解説見てから書いたコード int main(void) { int i,j,k,l; int N; int M[20]; static int table[100000]; int a,b; cin >> N; rep(i,N) cin >> M[i]; int n = pow((ull)2,(ull)N); for(i=0;i<n;i++) { a = i; int teikaSum = 0; rep(j,N) { if(a % 2) { teikaSum += M[j]; } a /= 2; } table[i] = teikaSum % 1000; /* char buf[100]; itoa(i, buf, 2); printf("table[%03s] = %d\n",buf,table[i]); */ } static int money[100000]; for(i=0;i<N;i++) { int c[20]; rep(j,N-1-i) c[j] = 0; for(;j<N;j++) c[j] = 1; // cは000001みたいな風 do { int d=0,e=1,f=0; int min=INT_MAX; // dにcを埋め込み rep(k,N) { d += e*c[k]; e <<= 1; } for(k=1;k<n;k<<=1,f++) { int g; if((d&k) == 0) continue; g = d-k; if(min > money[g] + max(0,M[f]-table[g])){ min = money[g] + max(0,M[f]-table[g]); } } money[d] = min; }while(next_permutation(c,c+N)); } cout << money[n-1] << endl; return 0; }