結果
問題 |
No.733 分身並列コーディング
|
ユーザー |
![]() |
提出日時 | 2019-03-02 10:37:10 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 54 ms / 1,500 ms |
コード長 | 1,167 bytes |
コンパイル時間 | 1,503 ms |
コンパイル使用メモリ | 167,236 KB |
実行使用メモリ | 25,280 KB |
最終ジャッジ日時 | 2024-06-23 12:16:47 |
合計ジャッジ時間 | 3,894 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 46 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define int long long #define pb push_back #define fi first #define se second #define rep(i,s,n) for(int i = s;i<n;i++) #define rrep(i,s,n) for(int i = (n)-1;i>=(s);i--) #define all(v) (v).begin(),(v).end() #define chmin(a,b) a=min((a),(b)) #define chmax(a,b) a=max((a),(b)) #define endl '\n' #define IOS() ios_base::sync_with_stdio(0);cin.tie(0) typedef long long ll; typedef pair<int,int>pint; typedef vector<int>vint; const ll MOD=1000000007,INF=1e18; int T,N; int t[100010]; int dp[1ll<<20][20]; signed main() { IOS(); cin>>T>>N; rep(i,0,N)cin>>t[i]; rep(i,1,(1ll<<N))rep(j,0,N)dp[i][j]=INF; rep(i,1,(1ll<<N)){ rep(j,0,N){ if(i&(1ll<<j)){ rep(k,0,N+1){ chmin(dp[i][k],dp[i^(1ll<<j)][k]+t[j]); if(dp[i][k]<=T){ dp[i][k+1]=0; } } } } } rep(i,1,N+1){ if(!dp[(1ll<<N)-1][i]){ cout<<i<<endl; return 0; } } return 0; }