oj.uz

Submission #100169

# Submission time Handle Problem Language Result Execution time Memory
100169 2019-03-09T18:13:43 Z sofhiasouza Kas (COCI17_kas) C++14
70 / 100
 518 ms 200128 KB 
#include <bits/stdc++.h>
#define MAXN 510
#define inf 0x3f3f3f3f
using namespace std;

int n, vet[MAXN], dp[MAXN][100010], sum = 0, sa[MAXN];

inline int func(int u, int s1)
{
	if(u == n+1 and s1 != 0) return inf;
	if(u == n+1) return 0;
	if(dp[u][s1] != -1) return dp[u][s1];

	int p1 = func(u+1, s1+vet[u]);
	int p2 = inf;
	if(vet[u] <= s1) p2 = func(u+1, s1-vet[u]);
	int p3 = func(u+1, s1) + vet[u];

	int menor = min({p1, p2, p3});

	if(s1 == 0) menor = min(menor, sum-sa[u-1]);
	return dp[u][s1] = menor;
}

int main()
{
	cin >> n;
	memset(dp, -1, sizeof dp);
	sa[0] = 0;
	for(int i = 1 ; i <= n ; i++)
	{
		cin >> vet[i];
		sum += vet[i];
		sa[i] = sa[i-1]+vet[i];
	}
	int result = func(1, 0);
	cout << (sum-result)/2 + result << endl;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 169 ms 200116 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 199900 KB Output is correct
2 Incorrect 159 ms 200036 KB Output isn't correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 199992 KB Output is correct
2 Incorrect 162 ms 199928 KB Output isn't correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 200028 KB Output is correct
2 Correct 161 ms 200000 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 199920 KB Output is correct
2 Correct 169 ms 199928 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 200076 KB Output is correct
2 Correct 169 ms 199924 KB Output is correct

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 199900 KB Output is correct
2 Correct 173 ms 199928 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 200056 KB Output is correct
2 Correct 233 ms 200128 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 300 ms 200000 KB Output is correct
2 Correct 518 ms 200056 KB Output is correct