oj.uz

Submission #113506

# Submission time Handle Problem Language Result Execution time Memory
113506 2019-05-26T03:46:39 Z CaQtiml Kas (COCI17_kas) C++14
100 / 100
 243 ms 196572 KB 
#include "bits/stdc++.h"
using namespace std;
const int INF = 1e9+29;
int arr[505];
int dp[505][100005];
int sum=0;
int n;

int main()
{
	//int n;
	cin >> n;
	for(int i=1;i<=n;i++)
	{
		cin >> arr[i];
		sum+=arr[i];
	}
	//memset(dp,-1,sizeof(dp));
	for(int i=0;i<=n;i++)
	{
		for(int j=0;j<=sum;j++)
		{
			dp[i][j]=INF;
		}
	}
	dp[0][0]=0;
	for(int i=1;i<=n;i++)
	{
		for(int diff=0;diff<=sum;diff++)
		{
			if(dp[i-1][diff]!=INF)
			{
				dp[i][diff] = min(dp[i][diff],arr[i]+dp[i-1][diff]);
				dp[i][diff+arr[i]] = min(dp[i-1][diff],dp[i][diff+arr[i]]);
				dp[i][abs(diff-arr[i])] = min(dp[i-1][diff],dp[i][abs(diff-arr[i])]);
			}
		}
	}
	int leftover = dp[n][0];
	//cout << leftover;
	sum-=leftover;
	sum/=2;
	sum+=leftover;
	cout << sum;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 412 KB Output is correct
2 Correct 2 ms 512 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 384 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 384 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 640 KB Output is correct
2 Correct 2 ms 684 KB Output is correct

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 79052 KB Output is correct
2 Correct 103 ms 98608 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 118136 KB Output is correct
2 Correct 166 ms 157240 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 176944 KB Output is correct
2 Correct 243 ms 196572 KB Output is correct