Submission #316493

---

Source Code Expand

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using sc = Scanner;

class Program
{

    static void Main(string[] args)
    {
        int n = sc.NextInt();
        int x = sc.NextInt();
        int[] weight  = new int[n];
        int answer = 0;
        for (int i = 0; i < n; i++)
        {
            weight[i] = sc.NextInt();
        }
        if (n == 1) // これに引っかかったくやしい
        {
            Console.WriteLine(weight[0] == x ? 1 : 0);
            return;
        }

        int[] zenhanDP = new int[1 << n/2];
        int[] kohanDP = new int[1 << n - n / 2];
        Dictionary<int,int> zenhanMultiElement = new Dictionary<int,int>();//要素と重複個数を格納,要素をO(logn)で検索可能
        Dictionary<int,int> kohanMultiElement = new Dictionary<int,int>();

        zenhanDP[1] = weight[0];
        for (int i = 1; i < n/2; i++)
            for (int j = 0 ; j < 1 << i ; j++)
                zenhanDP[(1 << i) + j] = zenhanDP[j] + weight[i];

        kohanDP[1] = weight[n/2];
        for (int i = 1; i < n - n/2; i++)
            for (int j = 0; j < 1 << i; j++)
                kohanDP[(1 << i) + j] = kohanDP[j] + weight[n/2 +i];

        Array.Sort(zenhanDP);
        Array.Sort(kohanDP);

        int tmp = zenhanDP[0];
        int tmpCount = 1;
        for (int i = 1; i < zenhanDP.Length; i++)
        {

            if(tmp != zenhanDP[i])
            {
                zenhanMultiElement.Add(tmp,tmpCount);
                tmp = zenhanDP[i];
                tmpCount = 1;
            }
            else
                tmpCount++;
            if(zenhanDP[i] > x) break; //目的値のxを超えた要素は答えにならない，ソートしてあるので以降は無駄
        }
        zenhanMultiElement.Add(tmp,tmpCount);

        tmp = kohanDP[0];
        tmpCount = 1;
        for (int i = 1; i < kohanDP.Length; i++)
        {
            if (tmp != kohanDP[i])
            {
                kohanMultiElement.Add(tmp, tmpCount);
                tmp = kohanDP[i];
                tmpCount = 1;
            }
            else
                tmpCount++;
            if (kohanDP[i] > x) break; //目的値のxを超えた要素は答えにならない，ソートしてあるので以降は無駄
        }
        kohanMultiElement.Add(tmp,tmpCount);

        foreach (var item1 in zenhanMultiElement)
        {
            int count = 0;
            if (kohanMultiElement.TryGetValue(x - item1.Key, out count)) // zenhan + kohan = xとなる要素があれば zenhancount * kohancountの組み合わせがある
            {
                answer += count * item1.Value;
            }
        }
        Console.WriteLine(answer);
    }
}
   
public static class Scanner
{
    public static string NextString()
    {
        string tmp = "";
        while (true)
        {
            string readData = char.ConvertFromUtf32(Console.Read());
            if (readData == " " || readData == "\n")
                break;
            tmp += readData;
        }
        return tmp;
    }

    public static string[] NextStrArray()
    {
        return Console.ReadLine().Split(' ');
    }

    public static long[] NextLongArray()
    {
        string[] s = NextStrArray();
        long[] a = new long[s.Length];
        for (int i = 0; i < a.Length; i++)
        {
            a[i] = long.Parse(s[i]);
        }
        return a;
    }
    public static int[] NextIntArray()
    {

        string[] s = NextStrArray();
        int[] a = new int[s.Length];
        for (int i = 0; i < a.Length; i++)
        {
            a[i] = int.Parse(s[i]);
        }
        return a;
    }
    public static int NextInt()
    {
        string tmp = "";
        while (true)
        {
            string readData = char.ConvertFromUtf32(Console.Read());
            if (readData == " " || readData == "\n")
                break;
        
            tmp += readData;
        }
        return int.Parse(tmp);
    }
    public static double NextDouble()
    {
        string tmp = "";
        while (true)
        {
            string readData = char.ConvertFromUtf32(Console.Read());
            if (readData == " " || readData == "\n")
                break;
            tmp += readData;
        }
        return double.Parse(tmp);
    }
    public static long NextLong()
    {
        string tmp = "";
        while (true)
        {
            string readData = char.ConvertFromUtf32(Console.Read());
            if (readData == " " || readData == "\n")
                break;
            tmp += readData;
        }
        return long.Parse(tmp);
    }
    public static double[] NextDoubleArray()
    {
        string[] s = NextStrArray();
        double[] a = new double[s.Length];
        for (int i = 0; i < a.Length; i++)
        {
            a[i] = double.Parse(s[i]);
        }
        return a;
    }
}

Submission Info

Judge Result