結果
問題 | No.2840 RGB Plates |
ユーザー |
|
提出日時 | 2024-08-09 22:48:58 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 921 ms / 2,000 ms |
コード長 | 729 bytes |
コンパイル時間 | 630 ms |
コンパイル使用メモリ | 70,336 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-08-18 00:59:25 |
合計ジャッジ時間 | 14,354 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#include<iostream> #include<algorithm> #include<cassert> using namespace std; const int L=100000; int N,A[3000]; int dp[2][L]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin>>N; for(int i=0;i<N;i++)cin>>A[i]; sort(A,A+N); reverse(A,A+N); int now=0; for(int j=0;j<L;j++)dp[now][j]=-1; int cur=0; for(int i=0;i<N;i++) { int nxt=1-now; for(int j=0;j<L;j++)dp[nxt][j]=-1; dp[nxt][A[i]]=cur; for(int j=0;j<L;j++)if(dp[now][j]>=0) { dp[nxt][j]=max(dp[nxt][j],dp[now][j]+A[i]); dp[nxt][abs(A[i]-j)]=max(dp[nxt][abs(A[i]-j)],dp[now][j]); if(j+A[i]<L)dp[nxt][j+A[i]]=max(dp[nxt][j+A[i]],dp[now][j]); } cur+=A[i]; now=nxt; } int ans=dp[now][0]; if(ans<=0)ans=-1; cout<<ans<<endl; }