oj.uz

Submission #1042155

# Submission time Handle Problem Language Result Execution time Memory
1042155 2024-08-02T15:29:19 Z biserailieva Kas (COCI17_kas) C++14
100 / 100
 103 ms 100700 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 100444 KB Output is correct
2 Correct 22 ms 100444 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 100444 KB Output is correct
2 Correct 22 ms 100556 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 100524 KB Output is correct
2 Correct 23 ms 100436 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 100516 KB Output is correct
2 Correct 25 ms 100508 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 100572 KB Output is correct
2 Correct 23 ms 100444 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 100432 KB Output is correct
2 Correct 23 ms 100444 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 100444 KB Output is correct
2 Correct 24 ms 100500 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 100428 KB Output is correct
2 Correct 27 ms 100604 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 100700 KB Output is correct
2 Correct 65 ms 100592 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 100688 KB Output is correct
2 Correct 81 ms 100696 KB Output is correct