Untitled

 avatar
unknown
plain_text
a year ago
1.2 kB
7
Indexable
using System;

class Program
{
    static void Main(string[] args)
    {
        int n = int.Parse(Console.ReadLine());
        string inputLine = Console.ReadLine();
        string[] values = inputLine.Split(' ');
        int[] A = Array.ConvertAll(values, int.Parse);
        
        int m = int.Parse(Console.ReadLine());
        inputLine = Console.ReadLine();
        values = inputLine.Split(' ');
        int[] P = Array.ConvertAll(values, int.Parse);
        
        // Create array B
        double[] B = new double[n * n];
        int index = 0;
        for (int j = 0; j < n; j++)
        {
            for (int i = 0; i <= j; i++)
            {
                B[index++] = A[i] * Math.Pow(2, j - i);
            }
        }
        
        foreach (var val in P)
        {
            Console.Write(IsPossible(B, val) ? "Yes " : "No ");
        }
    }
    
    static bool IsPossible(double[] B, int target)
    {
        int n = B.Length;
        bool[] dp = new bool[target + 1];
        dp[0] = true;

        foreach (var num in B)
        {
            for (int j = target; j >= num; j--)
            {
                dp[j] |= dp[j - (int)num];
            }
        }

        return dp[target];
    }
}
Editor is loading...
Leave a Comment