Submission #1347690

#	Time	Username	Problem	Language	Result	Execution time	Memory
1347690		jump	Kas (COCI17_kas)	C++20	In queue	0 ms	0 KiB

kas

#include <bits/stdc++.h>
#define int long long
int n;
int diff[2][100010];
//min unuse for i diff
signed main() {
	std::cin >> n;
	int sum=0;
	for(int d=1;d<=100000;d++)diff[0][d]=1e18,diff[1][d]=1e18;
	for(int i=0;i<n;i++){
		int in;
		std::cin >> in;
		sum+=in;
		for(int d=0;d<=50000;d++){
			diff[1][d]=std::min(diff[0][d]+in,diff[0][(std::abs(d-in))]);
			diff[1][d]=std::min(diff[1][d],diff[0][d+in]);
		}
		for(int d=0;d<=50000;d++)
		diff[0][d]=diff[1][d];
	}
	std::cout << (sum-diff[1][0])/2 + diff[1][0];
}