結果
問題 | No.1825 Except One |
ユーザー |
![]() |
提出日時 | 2022-01-28 22:24:27 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2,467 ms / 3,000 ms |
コード長 | 921 bytes |
コンパイル時間 | 2,111 ms |
コンパイル使用メモリ | 203,148 KB |
最終ジャッジ日時 | 2025-01-27 16:52:05 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 31 |
ソースコード
#include<bits/stdc++.h> using namespace std; int main(){ int N; cin>>N; vector<int> A; int mm=0; int ss=0; for (int i=0; i<N; i++){ int a; cin>>a; mm=max(mm,a); ss+=a; A.push_back(a); } vector<vector<vector<long long>>> dp(N+1,vector<vector<long long>>(mm+1,vector<long long>(ss+1,0))); dp[1][A[0]][A[0]]=1; dp[0][0][0]=1; long long ans=0; int thi=A[0]; for (int i=1; i<N; i++){ thi+=A[i]; for (int j=N; j>=1;j--){ for (int s=thi; s>=A[i]; s--){ for (int d=0; d<=A[i]; d++){ dp[j][A[i]][s]+=dp[j-1][d][s-A[i]]; } for (int d=A[i]+1; d<=mm; d++){ dp[j][d][s]+=dp[j-1][d][s-A[i]]; } } } } for (int j=2; j<=N; j++){ for (int k=0; k<=mm; k++){ for (int s=0; s<=ss; s++){ if ((s%(j-1)==0) && (k<=s/(j-1))){ ans+=dp[j][k][s]; } } } } cout<<ans<<endl; }