제출 #244824

#제출 시각아이디문제언어결과실행 시간메모리
244824VimmerKas (COCI17_kas)C++14
80 / 100
250 ms97820 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> //#pragma GCC optimize("unroll-loops") //#pragma GCC optimize("-O3") //#pragma GCC optimize("Ofast") //#pragma GCC optimize("fast-math") //#pragma GCC optimize("no-stack-protector") #define F first #define S second #define sz(x) int(x.size()) #define pb push_back #define N 100001 #define M ll(998244353) #define inf 1e9 + 1e9 using namespace std; using namespace __gnu_pbds; typedef long double ld; typedef long long ll; typedef short int si; typedef array <int, 3> a3; //typedef tree <int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; gp_hash_table <int, gp_hash_table <int, bool> > f[501]; int main() { //freopen("input.txt", "r", stdin); //freopen("output4.txt", "w", stdout); ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; int c[n], sumr = 0;; for (int i = 0; i < n; i++) {cin >> c[i]; sumr += c[i];} sort(c, c + n); reverse(c, c + n); bool dp[n + 1][N]; memset(dp, 0, sizeof(dp)); dp[0][0] = 1; for (int i = 0; i < n; i++) for (int j = 0; j < N; j++) if (dp[i][j]) { dp[i + 1][j] = 1; dp[i + 1][j + c[i]] = 1; } int sm = 0, sum = 0, ans = 1e9; for (int i = n; i >= 0; i--) { if (i != n) sm += c[i]; int val = sumr - sm; if (val % 2 || !dp[i][val / 2]) continue; sum = val / 2; ans = min(ans, sum + sm); } reverse(c, c + n); memset(dp, 0, sizeof(dp)); dp[0][0] = 1; for (int i = 0; i < n; i++) for (int j = 0; j < N; j++) if (dp[i][j]) { dp[i + 1][j] = 1; dp[i + 1][j + c[i]] = 1; } sm = 0; sum = 0; for (int i = n; i >= 0; i--) { if (i != n) sm += c[i]; int val = sumr - sm; if (val % 2 || !dp[i][val / 2]) continue; sum = val / 2; ans = min(ans, sum + sm); } if (n <= 50) { f[0][0][0] = 1; for (int i = 0; i < n; i++) for (auto it : f[i]) for (auto itr : it.S) { f[i + 1][it.F][itr.F] = 1; f[i + 1][it.F + c[i]][itr.F] = 1; f[i + 1][it.F][itr.F + c[i]] = 1; } for (int i = 0; i < N; i++) if (f[n][i][i]) ans = min(ans, i + sumr - i - i); } cout << ans << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...