結果
問題 | No.1825 Except One |
ユーザー |
![]() |
提出日時 | 2022-01-28 21:54:56 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,037 ms / 3,000 ms |
コード長 | 3,663 bytes |
コンパイル時間 | 1,238 ms |
コンパイル使用メモリ | 135,212 KB |
最終ジャッジ日時 | 2025-01-27 16:30:22 |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 31 |
ソースコード
#include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <cmath> #include <vector> #include <set> #include <map> #include <unordered_set> #include <unordered_map> #include <queue> #include <ctime> #include <cassert> #include <complex> #include <string> #include <cstring> #include <chrono> #include <random> #include <bitset> #include <fstream> #include <array> #include <functional> #include <stack> #include <memory> using namespace std; #define int long long #define ii pair <int, int> #define app push_back #define all(a) a.begin(), a.end() #define bp __builtin_popcountll #define ll long long #define mp make_pair #define x first #define y second #define Time (double)clock()/CLOCKS_PER_SEC #ifdef LOCAL #define debug(x) std::cerr << #x << ": " << x << '\n'; #else #define debug(x) #endif #define FORI(i,a,b) for (int i = (a); i < (b); ++i) #define FOR(i,a) FORI(i,0,a) #define ROFI(i,a,b) for (int i = (b)-1; i >= (a); --i) #define ROF(i,a) ROFI(i,0,a) #define rep(a) FOR(_,a) #define each(a,x) for (auto& a: x) #define FORN(i, n) FORI(i, 1, n + 1) using vi = vector<int>; template <typename T> std::istream& operator >>(std::istream& input, std::pair <T, T> & data) { input >> data.x >> data.y; return input; } template <typename T> std::istream& operator >>(std::istream& input, std::vector<T>& data) { for (T& x : data) input >> x; return input; } template <typename T> std::ostream& operator <<(std::ostream& output, const pair <T, T> & data) { output << "(" << data.x << "," << data.y << ")"; return output; } template <typename T> std::ostream& operator <<(std::ostream& output, const std::vector<T>& data) { for (const T& x : data) output << x << " "; return output; } std::ostream& operator <<(std::ostream& output, const __int128 &x) { __int128 n = x; if (n == 0) { output << "0"; return output; } if (n < 0) { n = -n; output << "-"; } string s; while (n) { s += '0' + (n%10); n /= 10; } reverse(all(s)); cout << s; return output; } ll div_up(ll a, ll b) { return a/b+((a^b)>0&&a%b); } // divide a by b rounded up ll div_down(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down ll math_mod(ll a, ll b) { return a - b * div_down(a, b); } #define tcT template<class T #define tcTU tcT, class U tcT> using V = vector<T>; tcT> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; } // set a = min(a,b) tcT> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; } ll gcd(ll a, ll b) { while (b) { tie(a, b) = mp(b, a % b); } return a; } int Bit(int mask, int bit) { return (mask >> bit) & 1; } const int N = 51, M = 101; int n, a[N], dp[N][N * M][M]; signed main() { #ifdef LOCAL #else #define endl '\n' ios_base::sync_with_stdio(0); cin.tie(0); #endif cin >> n; FORN (i, n) cin >> a[i]; dp[0][0][0] = 1; int L = 0, lmx = 0; FORN (i, n) { for (int cnt = i - 1; cnt >= 0; --cnt) { FOR (s, L + 1) { FOR (mx, lmx + 1) { //debug(cnt); debug(s); debug(mx); dp[cnt + 1][s + a[i]][max(mx, a[i])] += dp[cnt][s][mx]; } } } L += a[i]; ckmax(lmx, a[i]); } int ans = 0; for (int cnt = n; cnt >= 2; --cnt) { FOR (s, L + 1) { FOR (mx, lmx + 1) { if (s % (cnt - 1) == 0 && mx <= s / (cnt - 1)) { ans += dp[cnt][s][mx]; } } } } cout << ans << endl; }