oj.uz

Submission #100241

# Submission time Handle Problem Language Result Execution time Memory
100241 2019-03-10T03:09:19 Z luciocf Kas (COCI17_kas) C++14
100 / 100
 692 ms 200184 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 510;
const int maxm = 1e5+10;
const int inf = 1e9+10;

int num[maxn], n;

int dp[maxn][maxm];

int solve(int pos, int soma)
{
	if (pos == n+1 && !soma) return 0;
	if (pos == n+1) return -inf;
	if (dp[pos][soma] != -1) return dp[pos][soma];

	int caso1 = num[pos]+solve(pos+1, soma+num[pos]);
	int caso2 = solve(pos+1, soma-num[pos]);
	int caso3 = solve(pos+1, soma);

	return dp[pos][soma] = max({caso1, caso2, caso3});
}

int main(void)
{
	int soma = 0;
	cin >> n;

	for (int i = 1; i <= n; i++)
	{
		cin >> num[i];
		soma += num[i];
	}

	memset(dp, -1, sizeof dp);

	cout << soma-solve(1, 0) << "\n";
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 199928 KB Output is correct
2 Correct 159 ms 199972 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 199972 KB Output is correct
2 Correct 169 ms 199896 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 199984 KB Output is correct
2 Correct 181 ms 199960 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 200004 KB Output is correct
2 Correct 166 ms 200004 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 200064 KB Output is correct
2 Correct 163 ms 200028 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 199940 KB Output is correct
2 Correct 171 ms 200184 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 199896 KB Output is correct
2 Correct 165 ms 199928 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 200092 KB Output is correct
2 Correct 208 ms 200080 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 276 ms 199984 KB Output is correct
2 Correct 381 ms 200116 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 528 ms 199980 KB Output is correct
2 Correct 692 ms 200056 KB Output is correct