結果
問題 |
No.4 おもりと天秤
|
ユーザー |
|
提出日時 | 2016-07-31 16:49:46 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,844 bytes |
コンパイル時間 | 1,086 ms |
コンパイル使用メモリ | 109,832 KB |
実行使用メモリ | 31,896 KB |
最終ジャッジ日時 | 2024-11-06 21:27:33 |
合計ジャッジ時間 | 8,138 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 18 TLE * 1 -- * 4 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System; namespace OmoriToTenbin3 { class Program { static int N; static int[] W; static int[] remainSum; static int totalHalf; static void Main(string[] args) { N = int.Parse(Console.ReadLine()); W = new int[N]; remainSum = new int[N]; string[] vals = Console.ReadLine().Split(' '); int total = 0; for (int i = 0; i < N; i++) { W[i] = int.Parse(vals[i]); total += W[i]; } if(total % 2 != 0) { Console.WriteLine("impossible"); return; } totalHalf = total / 2; Array.Sort(W); Array.Reverse(W); remainSum[N-1] = W[N-1]; for(int i=N-2; i >= 0; i--) { remainSum[i] = remainSum[i + 1] + W[i]; } if(Search(0, 0)) { Console.WriteLine("possible"); } else { Console.WriteLine("impossible"); } } static bool Search(int weight, int i) { if (weight == totalHalf) { return true; } else if(weight > totalHalf) { return false; } if (i >= N) { return false; } if(weight + remainSum[i] < totalHalf) { return false; } if(Search(weight+W[i], i+1)) { return true; } if(Search(weight, i+1)) { return true; } return false; } } }