結果
問題 | No.1825 Except One |
ユーザー |
![]() |
提出日時 | 2023-10-26 13:22:23 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2,641 ms / 3,000 ms |
コード長 | 1,102 bytes |
コンパイル時間 | 3,240 ms |
コンパイル使用メモリ | 253,992 KB |
実行使用メモリ | 417,536 KB |
最終ジャッジ日時 | 2024-09-25 12:23:24 |
合計ジャッジ時間 | 16,029 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 31 |
ソースコード
#include<bits/stdc++.h>using namespace std;using ll = long long;int main(){cin.tie(nullptr);ios::sync_with_stdio(false);int n;cin>>n;int sum = 0;vector<vector<vector<ll>>> dp(1,vector<vector<ll>>(sum+1,vector<ll>(101,0)));dp[0][0][0] = 1;for(int i = 0;i<n;i++){int a;cin>>a;sum += a;vector<vector<vector<ll>>> ndp(i+2,vector<vector<ll>>(sum+1,vector<ll>(101,0)));for(int j = 0;j<=i;j++){for(int k = 0;k<=sum-a;k++){for(int l = 0;l<=100;l++){int nl = max(l,a);ndp[j][k][l] += dp[j][k][l];ndp[j+1][k+a][nl] += dp[j][k][l];}}}swap(ndp,dp);}ll ans = 0;for(int i = 2;i<=n;i++){for(int j = 0;j<=sum;j++){for(int k = 0;k<=100;k++){if(j%(i-1)!=0) continue;int ni = j / (i-1);if(k-ni>0) continue;ans += dp[i][j][k];}}}cout<<ans<<endl;}