Submission #167810

#TimeUsernameProblemLanguageResultExecution timeMemory
167810Atill83Kas (COCI17_kas)C++14
60 / 100
2080 ms124676 KiB
#include <bits/stdc++.h> #define ff first #define ss second #define endl '\n' using namespace std; const long long INF = (long long) 1e18; const int mod = (int) 1e9+7; const int MAXN = (int) 1e5+5; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pii; typedef pair<ll,ll> pll; ll n; int ar[MAXN]; ll mx = INF, ans, sum; map <pair<pii, int>, bool> mp; int suf[MAXN]; void dp(int fark, int ind, int kul){ if(mx == 0) return; pair<pii, int> a = {{fark, ind}, kul}; if(mp[a]) return; mp[a] = 1; if(ind > n) return; if(fark > suf[ind]){ return; } if(fark == 0 && kul != 0){ if(sum - kul < mx){ ans = sum - kul/2; mx = sum - kul; //cout<<sum<<" "<<kul<<endl; } } dp(fark + ar[ind], ind + 1, kul + ar[ind]); dp(abs(fark - ar[ind]), ind + 1, kul + ar[ind]); dp(fark, ind + 1, kul); } int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr);cout.tie(nullptr); #ifdef Local freopen("../IO/int.txt","r",stdin); freopen("../IO/out.txt","w",stdout); #endif cin>>n; for(int i = 0; i < n; i++){ cin>>ar[i]; sum += ar[i]; } for(int i = n - 1; i >= 0; i--){ suf[i] = suf[i + 1] + ar[i]; } sort(ar, ar + n); reverse(ar, ar + n); dp(0, 0, 0); cout<<ans<<endl; #ifdef Local cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds "; #endif }
#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...