Submission #839227

#TimeUsernameProblemLanguageResultExecution timeMemory
839227teo_thrashKas (COCI17_kas)C++14
30 / 100
72 ms2000 KiB
#include<bits/stdc++.h> #define pb push_back using namespace std; typedef long long ll; typedef pair<int, int> pii; const int maxn=1e5+10; const int mod=1e9+7; int n; ll a[503]; ll dp[maxn], sum=0; ///dp[i] is the max sum of the subsequences that when split optimally, the 2 parts differ by i ll curr[maxn]; int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); for(int i=0; i<=sum; i++){ dp[i]=-INT_MAX; } dp[0]=0; cin>>n; for(int i=0; i<n; i++){ cin>>a[i]; sum+=a[i]; for(int j=0; j<=sum; j++){ curr[j]=dp[j]; } for(int j=a[i]; j<=sum; j++){ if(dp[j-a[i]]==-INT_MAX) continue; curr[j]=max(curr[j], dp[j-a[i]]+a[i]); } for(int j=a[i]; j<=sum-a[i]; j++){ if(dp[j+a[i]]==-INT_MAX) continue; curr[j-a[i]]=max(curr[j-a[i]], dp[j]); } for(int j=1; j<a[i]; j++){ if(dp[j]==-INT_MAX) continue; curr[a[i]-j]=max(curr[a[i]-j], dp[j]-j+a[i]); } for(int j=0; j<=sum; j++){ dp[j]=max(curr[j], dp[j]); } } cout<<sum-dp[0]<<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...