# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
88907 |
2018-12-09T18:56:17 Z |
heon |
Kas (COCI17_kas) |
C++11 |
|
776 ms |
396072 KB |
#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 |
1 |
Incorrect |
304 ms |
395768 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
351 ms |
395816 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
330 ms |
395908 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
301 ms |
395908 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
305 ms |
395908 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
339 ms |
395972 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
304 ms |
395972 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
436 ms |
396052 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
393 ms |
396072 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
776 ms |
396072 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |