Submission #1098122

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098122		vjudge1	Bank (IZhO14_bank)	Cpython 3	100 / 100	628 ms	3160 KiB

bank

def can_pay_all_salaries(N, M, salaries, banknotes):
    # Сортируем зарплаты и купюры в порядке убывания
    salaries.sort(reverse=True)
    banknotes.sort(reverse=True)
    used = [False] * M 
    def backtrack(idx):
        if idx == N:
            return True
        current_salary = salaries[idx]
        def dfs(start, total):
            if total == current_salary:
                if backtrack(idx + 1):
                    return True
                return False
            if total > current_salary:
                return False
            prev = -1
            for i in range(start, M):
                if not used[i] and total + banknotes[i] <= current_salary:
                    if banknotes[i] == prev:
                        continue 
                    used[i] = True
                    if dfs(i + 1, total + banknotes[i]):
                        return True
                    used[i] = False
                    prev = banknotes[i]
            return False
        return dfs(0, 0)
    return backtrack(0)
def main():
    import sys
    import sys
    input = sys.stdin.read
    data = input().split()
    ptr = 0
    N = int(data[ptr])
    M = int(data[ptr +1])
    ptr +=2
    salaries = []
    for _ in range(N):
        salaries.append(int(data[ptr]))
        ptr +=1
    banknotes = []
    for _ in range(M):
        banknotes.append(int(data[ptr]))
        ptr +=1
    total_salary = sum(salaries)
    total_banknotes = sum(banknotes)
    if total_salary > total_banknotes:
        print("NO")
        return
 
    if can_pay_all_salaries(N, M, salaries, banknotes):
        print("YES")
    else:
        print("NO")
 
if __name__ == "__main__":
    main()

• Subtask 1: 19 / 19
• Subtask 2: 25 / 25
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29