oj.uz

Submission #100160

# Submission time Handle Problem Language Result Execution time Memory
100160 2019-03-09T17:47:42 Z pamaj Kas (COCI17_kas) C++14
70 / 100
 902 ms 525312 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 100, maxm = 1e3 + 10, inf = 1e6;

int dp[maxn][maxm][maxm], v[maxn], n, pref[maxn];

int solve(int i, int val1, int val2)
{

	if(dp[i][val1][val2] != -1) return dp[i][val1][val2];

	if(i == n)
	{
		if(val1 == val2)
		{
			return (pref[n - 1] - val1);
		}
		else 
			return inf;
	}

	int caso1 = solve(i + 1, val1, val2);
	int caso2 = solve(i + 1, val1 + v[i], val2);
	int caso3 = solve(i + 1, val1, val2 + v[i]);

	return dp[i][val1][val2] = 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));

	cout << solve(0, 0, 0) << "\n"; 

}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 399712 KB Output is correct
2 Correct 305 ms 399628 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 399708 KB Output is correct
2 Correct 291 ms 399624 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 399612 KB Output is correct
2 Correct 362 ms 399636 KB Output is correct

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 381 ms 399548 KB Output is correct
2 Correct 376 ms 399688 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 902 ms 525312 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 885 ms 525312 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 813 ms 525312 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -