You have n items. Each object has a weight, the weight of the object numbered i is equal to x_i. You need to put them in a backpack that holds no more than Sg. At the same time, you want the TOTAL WEIGHT of ALL items in the backpack to be as large as possible and at the same time it (the total weight) to be ODD. If you cannot put an odd weight, you will enter 0.

Input data The first line gives the number of available items 0≤n≤25. The second line lists n numbers—the weights of the objects. The weights of the items do not exceed 10⁹. The third line contains the number 0≤S≤10¹⁸, a limit on the total weight of the items that will be placed in the backpack.

Output On the first line print the largest odd total weight of objects that can be put in a backpack.

**MY SOLUTION **

import sys
def max_odd_weight(n, weights, S):
 possible_sums = {0} 
 
 for weight in weights:
 current_sums = set(possible_sums) 
 for w in current_sums:
 new_sum = w + weight
 if new_sum <= S:
 possible_sums.add(new_sum) 
 max_odd_weight = 0
 for w in possible_sums:
 if w % 2 != 0 and w > max_odd_weight:
 max_odd_weight = w
 return max_odd_weight
n = int(sys.stdin.readline())
weights = list(map(int, sys.stdin.readline().split()))
S = int(sys.stdin.readline())
result = max_odd_weight(n, weights, S)
sys.stdout.write(str(result))

It's really fast BUT I have a problem passing tests (All correct but memory limit exceeded). Test data is hidden. How can I cut the usage of memory even more?

time limit for test - 3 seconds Memory limit per test - 256 megabytes input - standard input output - standard output

using SYS helped, but not much

You have n items. Each object has a weight, the weight of the object numbered i is equal to x_i. You need to put them in a backpack that holds no more than Sg. At the same time, you want the TOTAL WEIGHT of ALL items in the backpack to be as large as possible and at the same time it (the total weight) to be ODD. If you cannot put an odd weight, you will enter 0.

Input data The first line gives the number of available items 0≤n≤25. The second line lists n numbers—the weights of the objects. The weights of the items do not exceed 10^9. The third line contains the number 0≤S≤10^18, a limit on the total weight of the items that will be placed in the backpack.

Output On the first line print the largest odd total weight of objects that can be put in a backpack.

**MY SOLUTION **

import sys
def max_odd_weight(n, weights, S):
 possible_sums = {0} 
 
 for weight in weights:
 current_sums = set(possible_sums) 
 for w in current_sums:
 new_sum = w + weight
 if new_sum <= S:
 possible_sums.add(new_sum) 
 max_odd_weight = 0
 for w in possible_sums:
 if w % 2 != 0 and w > max_odd_weight:
 max_odd_weight = w
 return max_odd_weight
n = int(sys.stdin.readline())
weights = list(map(int, sys.stdin.readline().split()))
S = int(sys.stdin.readline())
result = max_odd_weight(n, weights, S)
sys.stdout.write(str(result))

It's really fast BUT I have a problem passing tests (All correct but memory limit exceeded). Test data is hidden. How can I cut the usage of memory even more?

time limit for test - 3 seconds Memory limit per test - 256 megabytes input - standard input output - standard output

using SYS helped, but not much

You have n items. Each object has a weight, the weight of the object numbered i is equal to x_i. You need to put them in a backpack that holds no more than Sg. At the same time, you want the TOTAL WEIGHT of ALL items in the backpack to be as large as possible and at the same time it (the total weight) to be ODD. If you cannot put an odd weight, you will enter 0.

Input data The first line gives the number of available items 0≤n≤25. The second line lists n numbers—the weights of the objects. The weights of the items do not exceed 109. The third line contains the number 0≤S≤1018, a limit on the total weight of the items that will be placed in the backpack.

Output On the first line print the largest odd total weight of objects that can be put in a backpack.

**MY SOLUTION **

import sys
def max_odd_weight(n, weights, S):
 possible_sums = {0} 
 
 for weight in weights:
 current_sums = set(possible_sums) 
 for w in current_sums:
 new_sum = w + weight
 if new_sum <= S:
 possible_sums.add(new_sum) 
 max_odd_weight = 0
 for w in possible_sums:
 if w % 2 != 0 and w > max_odd_weight:
 max_odd_weight = w
 return max_odd_weight
n = int(sys.stdin.readline())
weights = list(map(int, sys.stdin.readline().split()))
S = int(sys.stdin.readline())
result = max_odd_weight(n, weights, S)
sys.stdout.write(str(result))

It's really fast BUT I have a problem passing tests (All correct but memory limit exceeded). Test data is hidden. How can I cut the usage of memory even more?

time limit for test - 3 seconds Memory limit per test - 256 megabytes input - standard input output - standard output

using SYS helped, but not much

You have n items. Each object has a weight, the weight of the object numbered i is equal to x_i. You need to put them in a backpack that holds no more than Sg. At the same time, you want the TOTAL WEIGHT of ALL items in the backpack to be as large as possible and at the same time it (the total weight) to be ODD. If you cannot put an odd weight, you will enter 0.

Input data The first line gives the number of available items 0≤n≤25. The second line lists n numbers—the weights of the objects. The weights of the items do not exceed 10⁹. The third line contains the number 0≤S≤10¹⁸, a limit on the total weight of the items that will be placed in the backpack.

Output On the first line print the largest odd total weight of objects that can be put in a backpack.

**MY SOLUTION **

import sys
def max_odd_weight(n, weights, S):
 possible_sums = {0} 
 
 for weight in weights:
 current_sums = set(possible_sums) 
 for w in current_sums:
 new_sum = w + weight
 if new_sum <= S:
 possible_sums.add(new_sum) 
 max_odd_weight = 0
 for w in possible_sums:
 if w % 2 != 0 and w > max_odd_weight:
 max_odd_weight = w
 return max_odd_weight
n = int(sys.stdin.readline())
weights = list(map(int, sys.stdin.readline().split()))
S = int(sys.stdin.readline())
result = max_odd_weight(n, weights, S)
sys.stdout.write(str(result))

It's really fast BUT I have a problem passing tests (All correct but memory limit exceeded). Test data is hidden. How can I cut the usage of memory even more?

time limit for test - 3 seconds Memory limit per test - 256 megabytes input - standard input output - standard output

using SYS helped, but not much