oj.uz

Submission #702681

# Submission time Handle Problem Language Result Execution time Memory
702681 2023-02-24T19:17:21 Z Doncho_Bonboncho Kas (COCI17_kas) C++14
100 / 100
 153 ms 100656 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 100484 KB Output is correct
2 Correct 36 ms 100428 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 100512 KB Output is correct
2 Correct 43 ms 100492 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 100424 KB Output is correct
2 Correct 37 ms 100504 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 100428 KB Output is correct
2 Correct 37 ms 100488 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 100516 KB Output is correct
2 Correct 36 ms 100532 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 100460 KB Output is correct
2 Correct 37 ms 100428 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 100460 KB Output is correct
2 Correct 39 ms 100432 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 100528 KB Output is correct
2 Correct 45 ms 100440 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 100552 KB Output is correct
2 Correct 91 ms 100552 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 100556 KB Output is correct
2 Correct 130 ms 100656 KB Output is correct