結果
問題 |
No.4 おもりと天秤
|
ユーザー |
![]() |
提出日時 | 2016-06-01 19:47:51 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 176 ms / 5,000 ms |
コード長 | 907 bytes |
コンパイル時間 | 3,623 ms |
コンパイル使用メモリ | 77,460 KB |
実行使用メモリ | 58,944 KB |
最終ジャッジ日時 | 2024-06-26 09:34:19 |
合計ジャッジ時間 | 8,082 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 23 |
ソースコード
import java.util.*; public class Exercise44{ public static void main (String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] weight = new int[n]; int sum = 0; for (int i = 0; i < n; i++){ int x = sc.nextInt(); weight[i] = x; sum += x; } if(sum % 2 == 1){ System.out.println("impossible"); System.exit(0); } int[][] dp = new int[n + 1][sum + 1]; for(int i = 0; i < n + 1; i++){ for (int j = 1; j < sum + 1; j++){ dp[i][j] = -1; } } for(int a = 0; a < n; a++){ for(int b = 0; b < sum; b++){ if(dp[a][b] >= 0){ dp[a + 1][b] = dp[a][b]; dp[a + 1][b + weight[a]] = dp[a][b] + weight[a]; } } } if (dp[n][sum / 2] >= 0){ System.out.println("possible"); }else{ System.out.println("impossible"); } } }