Submission #839101

#TimeUsernameProblemLanguageResultExecution timeMemory
839101carot15Kas (COCI17_kas)C++14
100 / 100
310 ms198004 KiB
// carot15 #include<bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define all(x) begin(x), end(x) #define mp make_pair #define cyd {cout<<"Yes";return;} #define cyn {cout<<"No";return;} const ll nmax=1e5+5; const ll mod=1e9+7; const int X[]={0,0,1,-1}; const int Y[]={-1,1,0,0}; int n,a[505],t=0,b[505][nmax]; int solve2(int i,int d) { if (i==n+1) return d == nmax ? 0 : 1e9; int &k=b[i][d]; if (~k) { return k; } return k=min({solve2(i+1,d-a[i]),solve2(i+1,d+a[i]),solve2(i+1,d)+a[i]}); } void solve(){ cin>>n; for (int i=1;i<=n;i++){ cin>>a[i]; t+=a[i]; } memset(b,-1,sizeof b); int ans=solve2(1,nmax); cout<<(t-ans)/2+ans; } /* 10 14 36 63 560 150 28 35 70 10 34 780 */ int main(){ ios_base::sync_with_stdio(false); cin.tie(0);cout.tie(0); // freopen(".INP", "r", stdin); // freopen(".OUT", "w", stdout); int T=1; // cin>>T; while(T--){ solve(); cout<<'\n'; } }
#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...