Submission #702681

#	Time	Username	Problem	Language	Result	Execution time	Memory
702681		Doncho_Bonboncho	Kas (COCI17_kas)	C++14	100 / 100	153 ms	100656 KiB

kas

#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const int MAX_S = 1e5 + 42;
const int MAX_N = 512;
const int INF = 1e9;
const int mod = 1e9 + 7;

int dp[MAX_N][MAX_S/2];

int a[MAX_N];
int sum;
int n;


int sol( int pos, int diff ){
	if( diff > sum / 2 ) return -INF;
	if( dp[pos][diff] != -1 ) return dp[pos][diff];
	if( pos == n ){
		if( diff == 0 ) return 0;
		return -INF;
	}

	int currNas = 0;
	currNas = std::max({ sol(pos+1, diff), sol(pos+1, diff + a[pos]) + a[pos], sol( pos+1, abs( diff - a[pos] ) ) + std::max(0, a[pos] - diff) } );
	return dp[pos][diff] = currNas;
}


int main () {

	std::cin>>n;
	for( int i=0 ; i<n ; i++ ){
		std::cin>>a[i];
		sum += a[i];
	}
	
	std::memset( dp, -1, sizeof(dp) );
	
	int nas = sol( 0, 0 );
	//std::cerr<<" ! "<<nas<<"\n";
	nas += ( sum - nas*2 );
	
	std::cout<<nas<<"\n";

	return 0;
}

• 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