結果
問題 |
No.733 分身並列コーディング
|
ユーザー |
![]() |
提出日時 | 2019-03-18 16:35:51 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 185 ms / 1,500 ms |
コード長 | 560 bytes |
コンパイル時間 | 812 ms |
コンパイル使用メモリ | 30,080 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-18 11:10:32 |
合計ジャッジ時間 | 5,652 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 46 |
ソースコード
#include<stdio.h> #include<stdlib.h> void run(void){ int t,n; scanf("%d%d",&t,&n); int *a=(int *)calloc(n,sizeof(int)); int i; for(i=0;i<n;i++) scanf("%d",a+i); int *dp=(int *)calloc(1<<n,sizeof(int)); for(i=1;i<(1<<n);i++){ int sum=0; int j; for(j=0;j<n;j++) if((i>>j)&1) sum+=a[j]; if(sum<=t){ dp[i]=1; continue; } int min=n; for(j=i&(i-1);j>0;j=(j-1)&i){ int m=dp[j]+dp[i^j]; if(min>m) min=m; } dp[i]=min; } printf("%d\n",dp[(1<<n)-1]); } int main(void){ run(); return 0; }