# |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
88906 |
2018-12-09T18:54:43 Z |
heon |
Kas (COCI17_kas) |
C++11 |
|
554 ms |
525312 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;
ll dp[100005][505];
ll dp2[100005][505];
ll 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])});
}
ll 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;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
554 ms |
525312 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
476 ms |
525312 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
424 ms |
525312 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
530 ms |
525312 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
415 ms |
525312 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
476 ms |
525312 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
409 ms |
525312 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
370 ms |
525312 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
415 ms |
525312 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
410 ms |
525312 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |