結果
問題 | No.1861 Required Number |
ユーザー |
|
提出日時 | 2021-12-27 01:27:26 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 45 ms / 2,500 ms |
コード長 | 985 bytes |
コンパイル時間 | 1,450 ms |
コンパイル使用メモリ | 169,316 KB |
実行使用メモリ | 23,208 KB |
最終ジャッジ日時 | 2024-07-18 22:13:40 |
合計ジャッジ時間 | 4,136 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 42 RE * 4 |
ソースコード
#include <bits/stdc++.h> using namespace std; int main() { //入力 int N,K;cin>>N>>K; vector<int>A(N+1); for(int i=1;i<=N;i++)cin>>A[i]; //dpの前処理 bool dpl[N+2][K+1],dpr[N+2][K+1]; for(int i=0;i<N+2;i++)for(int j=0;j<=K;j++)dpl[i][j]=false,dpr[i][j]=false; //dpl[i][j]:=A_1~A_iから選んで、和をjにできるか //dpr[i][j]:=A_i~A_Nから選んで、和をjにできるか dpl[0][0]=true;dpr[N+1][0]=true; for(int i=1;i<=N;i++)for(int j=0;j<=K;j++) { dpl[i][j]=dpl[i-1][j]; if(j<A[i])continue; if(dpl[i-1][j-A[i]])dpl[i][j]=true; } for(int i=N;i>=1;i--)for(int j=0;j<=K;j++) { dpr[i][j]=dpr[i+1][j]; if(j<A[i])continue; if(dpr[i+1][j-A[i]])dpr[i][j]=true; } //判定 if(!dpl[N][K]){cout<<-1<<endl;return 0;} int ans=0; for(int i=1;i<=N;i++) { bool check=true; for(int j=0;j<=K;j++) if(dpl[i-1][j]&&dpr[i+1][K-j])check=false; if(check)ans++; } //出力 cout<<ans<<endl; }