제출 #126169

#제출 시각아이디문제언어결과실행 시간메모리
126169abacabaKas (COCI17_kas)C++14
0 / 100
136 ms2316 KiB
#include <bits/stdc++.h> using namespace std; const int inf = 2e9; const int N = 1e5 + 15; const int M = 5e2 + 15; int n, m, a[M], ans = inf, canbe; bool dp1[N], dp2[M][N]; int summ; int main() { cin >> n; for(int i = 1; i <= n; ++i) { cin >> a[i]; summ += a[i]; } dp1[0] = dp2[n + 1][0] = 1; for(int i = n; i; --i) for(int j = N - 1; j >= 0; --j) if(j + a[i] < N && dp2[i + 1][j]) dp2[i][j + a[i]] = 1; for(int i = 1; i <= n; ++i) { for(int j = N - 1; j >= 0; --j) if(j + a[i] < N && dp1[j]) dp1[j + a[i]] = true; for(int j = N - 1; j >= 1; --j) if(dp1[j] && dp2[i + 1][j]) { if(summ - 2 * j < ans) canbe = j; ans = min(ans, summ - 2 * j); } } cout << summ - canbe; return 0; }
#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...