Submission #631197

#TimeUsernameProblemLanguageResultExecution timeMemory
631197inksamuraiKas (COCI17_kas)C++17
100 / 100
373 ms1884 KiB
#include <bits/stdc++.h> using namespace std; #define rep(i,n) for(int i=0;i<n;i++) #define rng(i,c,n) for(int i=c;i<n;i++) #define per(i,n) for(int i=n-1;i>=0;i--) #define fi first #define se second #define pb push_back #define sz(a) (int)a.size() #define vec(...) vector<__VA_ARGS__> #define _3phCa4T ios::sync_with_stdio(0),cin.tie(0) typedef long long ll; using pii=pair<int,int>; using vi=vector<int>; void print(){cout<<'\n';} template<class h,class...t> void print(const h&v,const t&...u){cout<<v<<' ',print(u...);} // e void chmax(int &a,int b){ a=max(a,b); } signed main(){ _3phCa4T; int n; cin>>n; vi a(n); rep(i,n){ cin>>a[i]; } const int o=1e5+1,oo=2e5+11; vi dp(oo,-1e9),ndp(oo); dp[o]=0; rep(i,n){ ndp=dp; rep(j,oo){ if(dp[j]!=-1e9){ if(j+a[i]<oo){ chmax(ndp[j+a[i]],dp[j]+a[i]); } if(j-a[i]>=0){ chmax(ndp[j-a[i]],dp[j]+a[i]); } } } dp=ndp; } int sun=0; rep(i,n){ sun+=a[i]; } print(sun-dp[o]/2); }
#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...