Submission #227581

#TimeUsernameProblemLanguageResultExecution timeMemory
227581mohamedsobhi777Kas (COCI17_kas)C++14
90 / 100
633 ms216628 KiB
#include<bits/stdc++.h> using namespace std ; const int N = 1e5 + 7 ; int offset = 1e5 + 7 ; int n , sum; int a[N] ; int dp[552][N] ; int solve(int i , int k){ if(~dp[i][k])return dp[i][k] ; if(i==n)return (k==offset ? 0 : 1e9) ; return dp[i][k] = min( min( solve(i+1 , k + a[i]) , solve(i+1 , k - a[i]) ) , solve(i+1 , k) + a[i] ) ; } int main(){ memset(dp , -1 , sizeof dp) ; ios_base::sync_with_stdio(0) ; cin.tie(0); cin>>n ; for(int i = 0 ;i < n;i++){ cin>>a[i]; sum+=a[i] ; } int mn = solve(0 , offset) ; cout<<(sum - mn) /2 + mn ; 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...