結果
問題 | No.332 数列をプレゼントに |
ユーザー | ぴろず |
提出日時 | 2015-12-25 01:21:38 |
言語 | Java21 (openjdk 21) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,656 bytes |
コンパイル時間 | 3,344 ms |
コンパイル使用メモリ | 92,620 KB |
実行使用メモリ | 67,188 KB |
最終ジャッジ日時 | 2023-10-19 03:20:58 |
合計ジャッジ時間 | 15,455 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 166 ms
57,988 KB |
testcase_01 | AC | 166 ms
57,752 KB |
testcase_02 | AC | 144 ms
57,664 KB |
testcase_03 | AC | 143 ms
57,540 KB |
testcase_04 | AC | 140 ms
57,396 KB |
testcase_05 | AC | 207 ms
62,428 KB |
testcase_06 | AC | 209 ms
66,888 KB |
testcase_07 | AC | 219 ms
64,812 KB |
testcase_08 | AC | 208 ms
66,908 KB |
testcase_09 | AC | 169 ms
58,084 KB |
testcase_10 | AC | 178 ms
59,984 KB |
testcase_11 | AC | 198 ms
62,472 KB |
testcase_12 | AC | 220 ms
66,880 KB |
testcase_13 | AC | 209 ms
66,944 KB |
testcase_14 | AC | 187 ms
62,516 KB |
testcase_15 | AC | 224 ms
66,936 KB |
testcase_16 | AC | 212 ms
66,904 KB |
testcase_17 | AC | 216 ms
66,920 KB |
testcase_18 | WA | - |
testcase_19 | AC | 217 ms
66,936 KB |
testcase_20 | AC | 214 ms
66,936 KB |
testcase_21 | AC | 216 ms
66,904 KB |
testcase_22 | AC | 212 ms
66,892 KB |
testcase_23 | AC | 220 ms
66,932 KB |
testcase_24 | AC | 222 ms
64,904 KB |
testcase_25 | AC | 219 ms
66,964 KB |
testcase_26 | WA | - |
testcase_27 | AC | 223 ms
66,928 KB |
testcase_28 | AC | 223 ms
66,904 KB |
testcase_29 | AC | 220 ms
66,864 KB |
testcase_30 | WA | - |
testcase_31 | AC | 226 ms
66,864 KB |
testcase_32 | AC | 217 ms
66,844 KB |
testcase_33 | AC | 225 ms
66,940 KB |
testcase_34 | AC | 251 ms
66,964 KB |
testcase_35 | AC | 218 ms
66,828 KB |
testcase_36 | AC | 137 ms
57,304 KB |
testcase_37 | AC | 221 ms
66,844 KB |
testcase_38 | AC | 225 ms
66,944 KB |
testcase_39 | AC | 219 ms
66,944 KB |
testcase_40 | AC | 220 ms
66,928 KB |
testcase_41 | AC | 222 ms
66,860 KB |
testcase_42 | AC | 224 ms
66,948 KB |
testcase_43 | AC | 224 ms
65,144 KB |
testcase_44 | AC | 230 ms
66,924 KB |
testcase_45 | AC | 224 ms
66,732 KB |
testcase_46 | AC | 192 ms
62,496 KB |
ソースコード
package no332; import java.util.ArrayList; import java.util.Collections; import java.util.Scanner; public class Main { public static final int MAX = 100000; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); long x = sc.nextLong(); ArrayList<Pair> a = new ArrayList<>(); //i,a for(int i=0;i<n;i++) { int aa = sc.nextInt(); a.add(new Pair(i,aa)); } Collections.sort(a,(xx,yy)->Integer.compare(xx.a, yy.a)); int n2 = 0; for(Pair p:a) { if (p.a <= MAX) { n2++; }else{ break; } } boolean[][] dp = new boolean[n2+1][MAX+1]; dp[0][0] = true; for(int i=1;i<=n2;i++) { int w = a.get(i-1).a; for(int j=MAX;j>=0;j--) { if (j >= w) { dp[i][j] |= dp[i-1][j-w]; } dp[i][j] |= dp[i-1][j]; } } int n3 = n - n2; for(int i=0;i<1<<n3;i++) { long sum = 0; for(int j=0;j<n3;j++) { if ((i>>j&1)>0) { sum += a.get(n2 + j).a; } } if (sum > x) { continue; } if (x - sum <= MAX && dp[n2][(int) (x-sum)]) { boolean[] ans = new boolean[n]; for(int j=0;j<n3;j++) { if ((i>>j&1)>0) { ans[a.get(n2+j).i] = true; } } int now = (int) (x - sum); for(int i2=n2;i2>=1;i2--) { int w = a.get(i2-1).a; if (now >= w && dp[i2-1][now-w]) { ans[a.get(i2-1).i] = true; now -= w; } } StringBuilder sb = new StringBuilder(); for(int j=0;j<n;j++) { sb.append(ans[j] ? 'o' : 'x'); } System.out.println(sb); return; } } System.out.println("No"); } } class Pair { int i,a; public Pair(int i,int a) { this.i = i; this.a = a; } }