Submission #88907

#TimeUsernameProblemLanguageResultExecution timeMemory
88907heonKas (COCI17_kas)C++11
0 / 100
776 ms396072 KiB
#include<bits/stdc++.h> using namespace std; #define all(x) x.begin(), x.end() typedef vector <int> vi; typedef pair<int,int> ii; typedef long long ll; const int MOD = 1e9 + 7; vi v; int dp[100005][505]; int dp2[100005][505]; int f(int n, int ind, int prvi, int drugi, int ostalo){ // minimiziraj ostatak if(ind == n && prvi != drugi) return MOD; if(ind == n && prvi == drugi) return ostalo; if(dp[prvi + drugi][ind] != -1) return dp[prvi + drugi][ind]; return dp[prvi + drugi][ind] = min({f(n, ind + 1, prvi + v[ind], drugi, ostalo), f(n, ind + 1, prvi, drugi + v[ind], ostalo), f(n, ind + 1, prvi, drugi, ostalo + v[ind])}); } int g(int n, int ind, int prvi, int drugi, int ostalo, int target){ // maksimiziraj dobitak if(ind == n && ostalo != target) return -MOD; if(ind == n && prvi != drugi) return -MOD; if(ind == n && prvi == drugi && ostalo == target) return prvi; if(dp2[prvi + drugi][ind] != -1) return dp2[prvi + drugi][ind]; return dp2[prvi + drugi][ind] = max({g(n, ind + 1, prvi + v[ind], drugi, ostalo, target), g(n, ind + 1, prvi, drugi + v[ind], ostalo, target), g(n, ind + 1, prvi, drugi, ostalo + v[ind], target)}); } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); int n; cin >> n; v.resize(n); memset(dp, -1, sizeof(dp)); memset(dp2, -1, sizeof(dp2)); for(int i = 0; i < n; i++){ cin >> v[i]; } int left = f(n, 0, 0, 0, 0); cout << g(n, 0, 0, 0, 0, left) + left; }
#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...