oj.uz

Submission #100179

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

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

inline int func(int u, int s1)
{
	if(u == n+1 and s1 != 100000) 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 = func(u+1, s1-vet[u]);
	int p3 = func(u+1, s1);
	if(p3 != inf) p3 += vet[u];

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

	if(s1 == 100000) 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, 100000);
	cout << (sum-result)/2 + result << endl;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 281 ms 399608 KB Output is correct
2 Correct 281 ms 399608 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 304 ms 399636 KB Output is correct
2 Correct 312 ms 399608 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 399556 KB Output is correct
2 Correct 294 ms 399608 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 290 ms 399496 KB Output is correct
2 Correct 300 ms 399520 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 320 ms 399564 KB Output is correct
2 Correct 305 ms 399480 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 314 ms 399580 KB Output is correct
2 Correct 277 ms 399608 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 306 ms 399484 KB Output is correct
2 Correct 325 ms 399484 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 452 ms 399612 KB Output is correct
2 Correct 345 ms 399736 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 438 ms 399736 KB Output is correct
2 Correct 481 ms 399608 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 711 ms 399672 KB Output is correct
2 Correct 1174 ms 399660 KB Output is correct