Submission #1019826

#	Time	Username	Problem	Language	Result	Execution time	Memory
1019826		ZeroCool	Kas (COCI17_kas)	C++14	100 / 100	159 ms	3588 KiB

kas

#include <bits/stdc++.h>
using namespace std;
  
#define int long long
  
#define ll long long
#define ar array
#define ld long double
  
const int N = 5e5 + 20;
const int MOD = 1e9 + 7;
const int K = 700;
const int INF = 1e17;
const int LOG = 34;
const int X = 100005;


int dp[2][2 * X];

signed main(){ios::sync_with_stdio(false);cin.tie(0);   
	memset(dp[0], -1, sizeof dp[0]);
	int n;
	cin>>n;
	dp[0][X] = 0;
	int k = 0;
	int sum = 0;
	while(n--){
		
		int x;
		cin>>x;
		sum += x;
		for(int i = 0;i < 2 * X;i++)dp[k ^ 1][i] = dp[k][i];
		for(int i = 0;i < 2 * X;i++){
			if(dp[k][i] == -1)continue;
			if(i - x >= 0)dp[k ^ 1][i-x] = max(dp[k ^ 1][i-x], dp[k][i] + x);
			if(i + x < 2 * X)dp[k ^ 1][i+x] = max(dp[k ^ 1][i+x], dp[k][i] + x);
		}
		k ^= 1;
	}
	cout<<sum - dp[k][X] / 2;
}

// Te molam da raboti!

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10