結果

問題 No.332 数列をプレゼントに
ユーザー Himatsubushin
提出日時 2015-12-28 18:32:30
言語 C#(csc)
(csc 3.9.0)
結果
TLE  
実行時間 -
コード長 2,747 bytes
コンパイル時間 2,001 ms
コンパイル使用メモリ 105,600 KB
実行使用メモリ 26,752 KB
最終ジャッジ日時 2024-09-19 07:50:44
合計ジャッジ時間 6,334 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 11 TLE * 1 -- * 30
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

using System;
using System.Collections;

namespace No_332
{
	class MainClass
	{
        private struct Progression
        {
            public long value;
            public int number;
        }

        private static int n;
        private static long x;
        private static Progression[] S;
        private static ArrayList result = new ArrayList();

		public static void Main (string[] args)
        {
            ArrayList sumPos = new ArrayList();

            string[] data = Console.ReadLine().Split(' ');
            int.TryParse(data[0], out n);
            long.TryParse(data[1], out x);
            string[] output = new string[n];

            data = Console.ReadLine().Split(' ');
            S = new Progression[data.Length];
            for (int i = 0; i < data.Length; i++)
            {
                long.TryParse(data[i], out S[i].value);
                S[i].number = i;
            }

            long[] value = new long[S.Length];
            for (int i = 0; i < value.Length; i++)
                value[i] = S[i].value;

            Array.Sort(value, S);

            for (int i = S.Length - 1; S[i].value > x; i--)
                n = i;

            bool success = false;
            long sum = 0;

            for (int i = 0; i < n; i++)
                sum += S[i].value;
            if (sum >= x)
            {
                for (int i = 0; i < output.Length; i++)
                    output[i] = "x";

                for (int i = 0; i < n; i++)
                {
                    if (TotalCheck(i, 0, sumPos))
                    {

                        for (int j = 0; j < result.Count; j++)
                            output[(int)result[j]] = "o";

                        for (int j = 0; j < output.Length; j++)
                            Console.Write(output[j]);

                        Console.WriteLine();
                        success = true;
                        break;
                    }
                }
            }
            if (!success)
                Console.WriteLine("No");
        }

        private static bool TotalCheck(int pos, long sum, ArrayList sumPos)
        {
            sum += S[pos].value;
            
            if (sum == x)
            {
                sumPos.Add(S[pos].number);
                result = new ArrayList(sumPos);
                return true;
            }
            else if (sum < x)
            {
                for (int i = pos + 1; i < n; i++)
                {
                    sumPos.Add(S[pos].number);
                    if (TotalCheck(i, sum, sumPos))
                        return true;
                    sumPos.RemoveAt(sumPos.Count - 1);
                }
            }

            return false;
        }
	}
}
0