結果
問題 |
No.1825 Except One
|
ユーザー |
![]() |
提出日時 | 2023-01-16 23:44:22 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 242 ms / 3,000 ms |
コード長 | 1,025 bytes |
コンパイル時間 | 1,388 ms |
コンパイル使用メモリ | 116,156 KB |
最終ジャッジ日時 | 2025-02-10 03:59:47 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 31 |
ソースコード
#include <iostream> #include <vector> #include <cmath> #include <map> #include <set> #include <iomanip> #include <queue> #include <algorithm> #include <numeric> #include <deque> #include <complex> #include <cassert> using namespace std; int main(){ long long N, ans=0; cin >> N; vector<long long> A(N); for (int i=0; i<N; i++) cin >> A[i]; sort(A.begin(), A.end()); vector<vector<vector<long long>>> dp(N+1, vector(N+1, vector<long long>(5001))); for (int i=0; i<=N; i++) dp[i][0][0] = 1; for (int i=1; i<=N; i++){ for (int j=1; j<=N; j++){ for (int k=0; k<=5000; k++){ dp[i][j][k] += dp[i-1][j][k]; if (k>=A[i-1]) dp[i][j][k] += dp[i-1][j-1][k-A[i-1]]; } } } for (int i=0; i<N; i++){ for (int j=1; j<N; j++){ for (int k=0; k<=5000; k++){ if ((k+A[i])%j == 0 && k+A[i]>=j*A[i]) ans += dp[i][j][k]; } } } cout << ans << endl; return 0; }