oj.uz

Submission #100157

# Submission time Handle Problem Language Result Execution time Memory
100157 2019-03-09T17:46:32 Z pamaj Kas (COCI17_kas) C++14
60 / 100
 423 ms 399920 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 50, 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 155 ms 199928 KB Output is correct
2 Correct 153 ms 199928 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 199928 KB Output is correct
2 Correct 157 ms 199996 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 200096 KB Output is correct
2 Correct 155 ms 199948 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 200000 KB Output is correct
2 Correct 152 ms 199928 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 199952 KB Output is correct
2 Correct 169 ms 200000 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 199964 KB Output is correct
2 Correct 172 ms 199988 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 200064 KB Output is correct
2 Runtime error 374 ms 399884 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 375 ms 399884 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 423 ms 399888 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 410 ms 399920 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -