# |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
100206 |
2019-03-09T19:57:38 Z |
pamaj |
Kas (COCI17_kas) |
C++14 |
|
703 ms |
391888 KB |
#include <bits/stdc++.h>
using namespace std;
const int maxn = 500, maxm = 1e5 + 10, inf = 1e6;
int dp[maxn][2*maxm], v[maxn], n, pref[maxn], rp;
int solve(int i, int val, int cont)
{
if(val == maxm)
{
rp = max(rp, cont);
}
if(dp[i][val] != -1) return dp[i][val];
if(i == n)
{
return (abs(maxm - val));
}
int caso1 = solve(i + 1, val, cont);
int caso2 = solve(i + 1, val + v[i], cont + v[i]);
int caso3 = solve(i + 1, val - v[i], cont);
return dp[i][val] = min({caso1, caso2, caso3});
}
int main()
{
ios::sync_with_stdio(false), cin.tie(nullptr);
cin >> n;
for(int i = 0; i < n; i++)
{
cin >> v[i];
pref[i] = v[i];
if(i) pref[i] += pref[i - 1];
}
memset(dp, -1, sizeof(dp));
int ans = solve(0, maxm, 0);
//cout << ans << "\n";
cout << rp + (pref[n - 1] - 2*rp) << "\n";
}
Compilation message
kas.cpp: In function 'int main()':
kas.cpp:47:6: warning: unused variable 'ans' [-Wunused-variable]
int ans = solve(0, maxm, 0);
^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
326 ms |
391800 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
304 ms |
391696 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
307 ms |
391764 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
307 ms |
391740 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
317 ms |
391756 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
332 ms |
391716 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
334 ms |
391804 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
472 ms |
391824 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
472 ms |
391832 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
703 ms |
391888 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |