# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|
88907 | | heon | Kas (COCI17_kas) | C++11 | | 776 ms | 396072 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |