제출 #100207

#제출 시각아이디문제언어결과실행 시간메모리
100207Leonardo_PaesKas (COCI17_kas)C++11
100 / 100
1463 ms400248 KiB
#include <bits/stdc++.h> using namespace std; #define MAXN 510 #define MAXM 100100 int n, sum, vet[MAXN], dp[MAXN][2*MAXM], prefsum[MAXN]; int solve(int pos, int val){ if(pos==n+1 and val!=100000)return 0x3f3f3f3f; if(pos==n+1){ return 0; } if(dp[pos][val]!=-1)return dp[pos][val]; int caso1 = solve(pos+1, val); int caso2 = solve(pos+1, val+vet[pos]); int caso3 = solve(pos+1, val-vet[pos]); if(caso1!=0x3f3f3f3f) caso1+=vet[pos]; int menor = min(min(caso1, caso2),caso3); if(val==100000)menor=min(menor, sum-prefsum[pos-1]); return dp[pos][val]=menor; } int main(){ cin >> n; for(int i=1; i<=n; i++){ cin >> vet[i]; prefsum[i]=vet[i]+prefsum[i-1]; sum+=vet[i]; } memset(dp, -1, sizeof dp); int ans = solve(0, 100000); cout << (sum-ans)/2 + 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...