제출 #1042155

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1042155		biserailieva	Kas (COCI17_kas)	C++14	100 / 100	103 ms	100700 KiB

kas

#include <bits/stdc++.h>
using namespace std;
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 = max({ sol(pos+1, diff), sol(pos+1, diff + a[pos]) + a[pos], sol( pos+1, abs( diff - a[pos] ) ) + max(0, a[pos] - diff) } );
	return dp[pos][diff] = currNas;
}
 
 
int main () 
{
	cin>>n;
	for( int i=0 ; i<n ; i++)
	{
		cin>>a[i];
		sum += a[i];
	}
	memset( dp, -1, sizeof(dp) );
	int nas = sol( 0, 0 );
	nas += ( sum - nas*2 );
	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