제출 #126167

#제출 시각아이디문제언어결과실행 시간메모리
126167abacabaKas (COCI17_kas)C++14
0 / 100
139 ms2276 KiB
#include <bits/stdc++.h> using namespace std; #define max3(a, b, c) max(a, max(b, c)) #define min3(a, b, c) min(a, min(b, c)) #define mp make_pair #define f first #define se second #define pb push_back #define ppb pop_back #define ll long long #define ull unsigned long long #define cntbit(x) __builtin_popcount(x) #define uset unordered_set #define umap unordered_map #define pii pair<int, int> #define ld long double #define pll pair<long long, long long> const int inf = 2e9; const int N = 1e5 + 15; const int M = 5e2 + 15; int n, m, a[M], ans; bool dp1[N], dp2[M][N]; int summ = 0; 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]) ans = max(ans, summ - j); } cout << ans << endl; 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...