結果
問題 |
No.4 おもりと天秤
|
ユーザー |
![]() |
提出日時 | 2016-01-20 15:57:52 |
言語 | Java (openjdk 23) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,182 bytes |
コンパイル時間 | 2,120 ms |
コンパイル使用メモリ | 77,092 KB |
実行使用メモリ | 37,372 KB |
最終ジャッジ日時 | 2024-09-21 14:47:47 |
合計ジャッジ時間 | 4,188 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 11 WA * 10 RE * 2 |
ソースコード
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; public class Main { public static void main(String[] args) { BufferedReader stdReader =new BufferedReader(new InputStreamReader(System.in)); try { int N = Integer.parseInt(stdReader.readLine()); String[] temps = stdReader.readLine().split(" "); int[] nums = new int[N+1]; int sum = 0; for(int i=0;i<N;i++){ nums[i+1] = Integer.parseInt(temps[i]); sum += nums[i+1]; } if(sum%2 != 0){ System.out.println("impossible"); return; } Arrays.sort(nums); int half = sum/2; boolean[] dp = new boolean[half+1]; dp[nums[1]] = true; for(int i=2;i<nums.length;i++){ dp[nums[i]] = true; for(int j=1;j<half+1;j++){ if(j > nums[i]) break; if(dp[j] && j+nums[i] <= half) dp[j+nums[i]] = true; } } if(dp[half]) System.out.println("possible"); else System.out.println("impossible"); } catch (IOException e) { e.printStackTrace(); } } }